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

Мне нужно сгенерировать все возможные комбинации из 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)
Источник

2 ответа

Решение

Вот пара селекторов, которые вы могли бы расширить 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)
Источник

Позвольте мне реализовать это в SequenceableCollection ради простоты:

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

ДОПОЛНЕНИЕ

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

Источник
Другие вопросы по тегам