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)