Smalltalk中的重复组合

问题描述：

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

问题输入：我有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)

smalltalk生活！最后在20年前从野外听到。 – javadba

@javadba即使他们不再流行于流行的发行版，学习诸如Smalltalk等语言的方面也是有益的。我从好奇心中学习了Smalltalk，从多年以来我听到的一切。我很惊讶Ruby从Smalltalk中解脱了多少。这让我改进了一些关于现代语言编程的思考方式。我不知道你是否尝试过Smalltalk，但它很有趣。 :)如果你真的想挑选某人，请查看[pdp-11标签]（http://stackoverflow.com/questions/tagged/pdp-11）。 :) – lurker

Smalltalk程序员在遥远的过去当时被广泛推崇。当面试拥有ST的C++作业时，几乎是“你没事了”（我遇到过每个ST程序员）。除了在大型电信设备的孤立情况下，我不认为它还活着。 – javadba

答

这里有几个选择器，您可以使用它们来扩展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)

答

让我在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同样的技术。

Smalltalk中的重复组合

相关推荐