Combinations WITH repetitions in Smalltalk

Question

I need to generate all the possible combinations of N numbers including repetitions.

Problem input: I have N cells where I can put one number in the interval 0 to: 9, in each cell.

Wrong solution (with N = 4):

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

Does not includes #(0 0 0 0) , #(1 1 1 1) , #(2 2 2 2), etc.

Expected output (with N = 2, and range 1-4 for the sake of brevity):

#(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

Here are a couple of selectors with which you could extend SequenceableCollection. That's the class where permutationsDo: is defined and is inherited, ultimately, by the Interval class.

Category "enumerating":

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

Category "private":

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) ] ] ]

So now you can do:

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

Which yields:

#(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)

This selector operates "symmetrically" like the existing permutationsDo: selector does, which is the number of elements in the resulting arrays (number of choices) is the same as the number of values in the collection.

---

You can easily go from that to a more general solution:

Under "enumerating":

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 ]

Under "private":

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) ] ] ]

Here's an example:

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

Which yields:

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

Answer 2

Let me implement this in SequenceableCollection for the sake of simplicity:

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

The idea is the following: Use the lexicographic order to sort all combinations. In other words:

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

if ai = bi for all i below some index j where aj < bj.

With this order the first combination is (0, ..., 0) and the last one (9, ..., 9).

Moreover, given a combination (a1, ..., an) the next one in this order is the one that adds 1 to the lowest preeminent index, this is the last index j where aj < 9. For example the next to (2, 3, 8, 9) is (2, 3, 9, 9) as there can't be anything in between.

Once we get to (9, ..., 9) we are done, and answer with nil.

Be aware that the method above modifies the receiver, which is why we have to copy in the script below.

Here is the script that produces all combinations (n is your 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

The same technique can be used for other problems of similar nature.