スモールトークで繰り返しの組み合わせ

Question

の可能な組み合わせをすべての繰り返しを含むように生成する必要があります。

問題入力：私はN個のセルを持っています。ここでは、各セルに0〜：9の間に1つの数値を入れることができます。

間違っ溶液（とN = 4）：

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

は＃（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でこれを実装してみましょう簡潔さのために：

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) 

iすべてのためのai = biかのいくつかの指標jaj < bj以下：他の言葉で。

この順序では、最初の組み合わせは(0, ..., 0)で、最後のものは(9, ..., 9)です。

また、組み合わせ(a1, ..., an)所定の順で次のは、これが最後のインデックスjaj < 9で、最低抜群インデックスに1を付加するものです。たとえば、(2, 3, 8, 9)の次の文字は(2, 3, 9, 9)なので、間に何も入れることはできません。

(9, ..., 9)になると、完了し、nilと回答します。

上記の方法で受信者が変更されていることに注意してください。その理由は、下記のスクリプトにcopyが必要な理由です。ここで

は補遺同じ技術が同様の性質の other problemsのために使用することができる

（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 

---

すべての組み合わせを生成するスクリプトです。