从Smalltalk中的集合生成所有组合

Question

我看到C＃和其他语言已解决此问题，但Smalltalk无法解决此问题。我有3个系列，例如：

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

我需要做所有可能的组合， Ë：

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

我已经看到了佳乐和菲罗有组合：atATimeDo：但我不明白如何使用它对于这种情况。这不是功课。任何帮助？

Answer 1

这里是Smalltalk/X的类库（在SequentialCollection中）的代码。 请参阅最后使用示例的注释。

---

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

Answer 2

这是一个有点神秘，但短期。它使用块作为匿名函数（有点类似，它仍然需要从变量中引用，以便可以递归调用它）。

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

Answer 3

组合的目的：atATimeDo：是计算给定大小的分区。
要获得笛卡尔产品，Martin Kobetic提供的递归功能版本是最短的代码。
这是一个迭代变体：

| 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