Комбинации с повторениями в Smalltalk

Question

Мне нужно сгенерировать все возможные комбинации из N чисел включая повторений.

Проблема ввода: У меня есть N ячеек, где я могу поместить одно число в интервале от 0 до: 9 в каждой ячейке.

Неправильный раствор (с N = 4):

(0 to: 3) permutationsDo: [ : each | Transcript cr; show: each printString]. 

Не включает в себя # (0 0 0 0), # (1 1 1 1), # (2 2 2 2), и т.д. .

Ожидаемые результаты (с N = 2, и диапазон 1-4 для краткости):

#(1 1) 
#(2 2) 
#(3 3) 
#(4 4) 
#(2 1) 
#(3 2) 
#(4 3) 
#(1 4) 
#(3 1) 
#(4 2) 
#(1 3) 
#(2 4) 
#(4 1) 
#(1 2) 
#(2 3) 
#(3 4) 

Answer 1

Вот пара селекторов, с которыми вы могли бы расширить SequenceableCollection. Это класс, где permutationsDo: определен и наследуется, в конечном счете, классом Interval.

Категория "перечисляя":

enumerationsDo: aBlock 
    | anArray | 
    anArray := Array new: self size. 
    self enumerateWithSize: (self size) in: anArray do: [ :each | aBlock value: each ] 

Категория "частный":

enumerateWithSize: aSize in: anArray do: aBlock 
    (aSize = 1) 
     ifTrue: [ 
     self do: [ :each | 
      aBlock value: (anArray at: (self size - aSize + 1) put: each ; yourself) ] ] 
     ifFalse: [ 
     self do: [ :each | 
      self enumerateWithSize: (aSize - 1) in: anArray do: [ :eachArray | 
       aBlock value: (eachArray at: (self size - aSize + 1) put: each ; yourself) ] ] ] 

Итак, теперь вы можете сделать:

(0 to: 2) enumerationsDo: [ :each | Transcript show: each printString ; cr ] 

Что дает:

#(0 0 0) 
#(0 0 1) 
#(0 0 2) 
#(0 1 0) 
#(0 1 1) 
#(0 1 2) 
#(0 2 0) 
#(0 2 1) 
#(0 2 2) 
#(1 0 0) 
#(1 0 1) 
#(1 0 2) 
#(1 1 0) 
#(1 1 1) 
#(1 1 2) 
#(1 2 0) 
#(1 2 1) 
#(1 2 2) 
#(2 0 0) 
#(2 0 1) 
#(2 0 2) 
#(2 1 0) 
#(2 1 1) 
#(2 1 2) 
#(2 2 0) 
#(2 2 1) 
#(2 2 2) 

Этот селектор работает «симметрично», как это делает селектор permutationsDo:, который представляет собой количество элементов в результирующих массивах (количество вариантов), такое же, как и количество значений в коллекции.

---

Вы можете легко перейти от к более общему решению:

Под "перечисляя":

enumerationsDo: aBlock 
    self enumerationsOfSize: (self size) do: aBlock 

enumerationsOfSize: aSize do: aBlock 
    | anArray | 
    anArray := Array new: aSize. 
    self enumerateWithSize: aSize subSize: aSize in: anArray do: [ :each | aBlock value: each ] 

Под "частным":

enumerateWithSize: aSize subSize: sSize in: anArray do: aBlock 
    (aSize < sSize) 
     ifTrue: [ ^self error: 'subSize cannot exceed array size' ]. 
    (sSize < 1) 
     ifTrue: [ ^self error: 'sizes must be positive' ]. 

    (sSize = 1) 
     ifTrue: [ 
      self do: [ :each | 
       aBlock value: (anArray at: (aSize - sSize + 1) put: each ; yourself) ] ] 
     ifFalse: [ 
      self do: [ :each | 
       self enumerateWithSize: aSize subSize: (sSize - 1) in: anArray do: [ :eachArray | 
        aBlock value: (eachArray at: (aSize - sSize + 1) put: each ; yourself) ] ] ] 

Вот пример:

(1 to: 3) enumerationsOfSize: 2 do: [ :e | Transcript show: e printString ; cr ] 

Которые доходы:

#(1 1) 
#(1 2) 
#(1 3) 
#(2 1) 
#(2 2) 
#(2 3) 
#(3 1) 
#(3 2) 
#(3 3) 

Answer 2

Позвольте мне осуществить это в SequenceableCollection FO r для простоты:

nextCombination09 
    | j | 
    j := self findLast: [:ai | ai < 9] ifAbsent: [^nil]. 
    j + 1 to: self size do: [:i | self at: i put: 0]. 
    self at: j put: (self at: j) + 1 

Идея заключается в следующем: используйте лексикографический порядок для сортировки всех комбинаций. Другими словами:

(a1, ..., an) < (b1, ..., bn) 

если ai = bi для всех i ниже некоторого индекса j где aj < bj.

С этим заказом первая комбинация (0, ..., 0) и последняя (9, ..., 9).

Кроме того, учитывая сочетание (a1, ..., an) следующий в этом порядке является тот, который добавляет 1 к наименьшему первенствующее индексу, это последний индекс j где aj < 9. Например, рядом с (2, 3, 8, 9) находится (2, 3, 9, 9), так как между ними не может быть ничего.

Как только мы доберемся до (9, ..., 9), мы закончили и ответим nil.

Помните, что метод выше изменяет приемник, поэтому мы должны указать copy в приведенном ниже скрипте.

Вот скрипт, который производит все комбинации (n ваш N)

n := <whatever> 
    array := Array new: n withAll: 0. 
    combinations := OrderedCollection new: (10 raisedTo: n). 
    [ 
    combinations add: array copy. 
    array nextCombination09 notNil] whileTrue. 
    ^combinations 

---

ADDENDUM

Тот же метод может быть использован для other problems аналогичного характера.