Smalltalk 中重复的组合
Combinations WITH repetitions in Smalltalk
我需要生成 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)
为了简单起见,让我在 SequenceableCollection
中实现它:
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)
if 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 类似的性质。
这里有几个选择器,您可以使用它们来扩展 SequenceableCollection
。那就是 class,其中 permutationsDo:
被定义并最终被 Interval
class 继承。
类别"enumerating":
enumerationsDo: aBlock
| anArray |
anArray := Array new: self size.
self enumerateWithSize: (self size) in: anArray do: [ :each | aBlock value: each ]
类别"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) ] ] ]
现在你可以做:
(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:
选择器相同 "symmetrically",即结果数组中的元素数量(选择数量)与集合中的值数量相同.
您可以轻松地从那个转向更通用的解决方案:
在"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 ]
在"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) ] ] ]
这是一个例子:
(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)
我需要生成 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)
为了简单起见,让我在 SequenceableCollection
中实现它:
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)
if 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 类似的性质。
这里有几个选择器,您可以使用它们来扩展 SequenceableCollection
。那就是 class,其中 permutationsDo:
被定义并最终被 Interval
class 继承。
类别"enumerating":
enumerationsDo: aBlock
| anArray |
anArray := Array new: self size.
self enumerateWithSize: (self size) in: anArray do: [ :each | aBlock value: each ]
类别"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) ] ] ]
现在你可以做:
(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:
选择器相同 "symmetrically",即结果数组中的元素数量(选择数量)与集合中的值数量相同.
您可以轻松地从那个转向更通用的解决方案:
在"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 ]
在"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) ] ] ]
这是一个例子:
(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)