Generating all combinations from collections in Sm

问题:

I've seen this problem resolved for C# and other languages but not for Smalltalk. I have 3 collections, for example:

a := #(3 4 5).
b := #(4 1 2).
c := #(5 2 3).

and I need to make all possible combinations, i. e.:

#(3 4 5)
#(3 4 2)
#(3 4 3)

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

#(3 2 5)
#(3 2 2)
#(3 2 3)

#(4 4 5)
...

I have seen in Squeak and Pharo there is combinations:atATimeDo: but I don't get how to use it for this case. This is not homework. Any help?

回答1:

here is the code from Smalltalk/X's class library (in SequentialCollection). See the example-use comments at the end.

---

combinationsDo: aBlock
    "Repeatly evaluate aBlock with all combinations of elements from the receivers elements. 
     The receivers elements must be collections of the individuals to be taken for the combinations"

    self combinationsStartingAt:1 prefix:#() do:aBlock

---

combinationsStartingAt:anInteger prefix:prefix do:aBlock
    "a helper for combinationsDo:"

    |loopedElement|

    loopedElement := self at:anInteger.

    anInteger == self size ifTrue:[
        loopedElement do:[:el | aBlock value:(prefix copyWith:el)].
        ^ self.
    ].

    loopedElement do:[:el |
        |newPrefix|

        newPrefix := (prefix copyWith:el).
        self combinationsStartingAt:anInteger+1 prefix:newPrefix do:aBlock
    ].

    "
     (Array 
            with:($a to:$d)
            with:(1 to: 4)) 
        combinationsDo:[:eachCombination | Transcript showCR: eachCombination]
    "
    "
     (Array 
            with:#(1 2 3 4 5 6 7 8 9)
            with:#(A)) 
        combinationsDo:[:eachCombination | Transcript showCR: eachCombination]
    "
    "
     #( (3 4 5) 
        (4 1 2)
        (5 2 3) 
     ) combinationsDo:[:eachCombination | Transcript showCR: eachCombination]
    "

回答2:

This is a bit cryptic, but short. It uses the block as an anonymous function (sort of, it still needs to be referenced from a variable so that it can be called recursively).

| expand |
expand := [ :prefix :lists |
    lists isEmpty
        ifTrue: [ Array with: prefix ]
        ifFalse: [ | tail |
            tail := lists allButFirst: 1.
            lists first inject: #() into: [ :all :each |
                all, (expand value: (prefix copyWith: each) value: tail) ] ] ].
expand value: #() value: #((3 4 5)(4 1 2)(5 2 3)) 

回答3:

The purpose of combinations:atATimeDo: is to compute partitions of a given size.
To get the cartesian product, the recursive functional version provided by Martin Kobetic is the shortest code.
Here is an iterative variant:

| arrayOfArray n p cartesianProduct |
arrayOfArray := #(
    #(3 4 5)
    #(4 1 2)
    #(5 2 3)
).
n := arrayOfArray size.
p := arrayOfArray inject: 1 into: [:product :array | product * array size].
cartesianProduct := (Array new: p) collect: [:i | Array new: n].
1 to: p do: 
    [:iSol | 
    | packetIndex |
    packetIndex := iSol - 1.
    n to: 1 by: -1 do: 
        [:iVar | 
        | ni valuesOfIVar |
        ni := (valuesOfIVar := arrayOfArray at: iVar) size.
        (cartesianProduct at: iSol)
            at: iVar put: (valuesOfIVar at: packetIndex \\ ni + 1).
        packetIndex := packetIndex // ni]].
^cartesianProduct