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)

@javadba There are benefits to learning aspects of languages such as Smalltalk even though they may no longer be in popular circulation any more. I learned Smalltalk out of curiosity from what I had heard about it over many years. I was amazed at how much Ruby had lifted from Smalltalk. It's caused me to refine some of the ways I think about programming in modern languages. I don't know if you've tried Smalltalk, but it's fun. :) If you really want to pick on someone, go check out the [pdp-11 tag](http://stackoverflow.com/questions/tagged/pdp-11). :) — lurker, May 16 '16 at 14:12
Smalltalk programmers were widely respected at that time in the distant past. When interviewing for C++ jobs having ST was almost a "ok you're in" (per ST programmers I had met). I just did not think it were still alive except in isolated instances of large telecomm installations. — WestCoastProjects, May 16 '16 at 14:48
@javadba "alive" is a broad term I suppose. But your perception as to "how much alive" is true. Smalltalk has very little in the way of commercial applications, and it's not on any serious "trending now" charts. Even in modern times, though, I have seen recommendations that programmers have some breadth on their resumes to include languages that are "off the beaten path," including Smalltalk (see, for example, the book, "The Passionate Programmer" by Chad Fowler). — lurker, May 16 '16 at 15:18

score 2 · Answer 1 · edited May 23 '17 at 12:16

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.

lurker · Accepted Answer · 2016-05-23T16:40:06.750

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)

Combinations WITH repetitions in Smalltalk

2 Answers2