Smalltalk中的重复组合

Question

我需要生成N个号码的所有可能组合，包括重复。

问题输入：我有N个单元格，我可以在间隔0到9之间放置一个数字，在每个单元格中。

错误溶液（用N = 4）：

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

不包括＃（0 0 0 0），＃（1 1 1 1），＃（2 2 2 2）等。

预期输出（与N = 2，和范围1-4简洁起见）：

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

这里有几个选择器，您可以使用它们来扩展SequenceableCollection。这是定义permutationsDo:的类，最终由Interval类继承。

类别 “枚举”：

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

类别 “私”：

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

所以现在你可以这样做：

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

其中产量：

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

此选择器与“permutationsDo:”选择器的“对称”操作类似，它是结果数组中元素的数量（选项数）与集合中值的数量相同。

---

您可以轻松地从去一个更通用的解决方案：

在 “枚举”：

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 ] 

在 “私”：

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

下面是一个例子：

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

其中产量：

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

Answer 2

让我在SequenceableCollection实现此FO r简单起见：

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 

想法如下：使用字典顺序对所有组合进行排序。换句话说：对于

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

如果ai = bi所有i下面的一些指标j其中aj < bj。

使用此订单的第一个组合是(0, ..., 0)和最后一个(9, ..., 9)。

此外，在给定组合(a1, ..., an)下一个以该顺序是添加1到最低卓越指数之一，这是最后的索引j其中aj < 9。例如，(2, 3, 8, 9)的旁边是(2, 3, 9, 9)，因为两者之间不能有任何内容。

一旦我们到达(9, ..., 9)我们完成了，并回答nil。

请注意上面的方法修改了接收器，这就是为什么我们必须在下面的脚本中使用copy。

这里是产生所有组合的脚本（n是你N）

n := <whatever> 
    array := Array new: n withAll: 0. 
    combinations := OrderedCollection new: (10 raisedTo: n). 
    [ 
    combinations add: array copy. 
    array nextCombination09 notNil] whileTrue. 
    ^combinations 

---

附录

可用于类似性质的other problems同样的技术。