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)

來源

2016-05-14 user183928

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)

來源

2016-05-15 01:25:32 lurker

讓我在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同樣的技術。

來源

2016-05-14 21:36:52

Smalltalk中的重複組合

回答

相關問題