Combinaisons avec des répétitions dans Smalltalk

Question

J'ai besoin de générer toutes les combinaisons possibles de N nombres , y compris répétitions.

Problème d'entrée: J'ai des cellules N où je peux mettre un nombre dans l'intervalle 0 à: 9, dans chaque cellule.

solution incorrecte (avec N = 4):

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

ne comprend pas # (0 0 0 0), # (1 1 1 1), # (2 2 2 2), etc. .

sortie prévue (avec N = 2, et la gamme 1-4 pour un souci de concision):

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

Voici quelques sélecteurs avec lesquels vous pouvez étendre SequenceableCollection. C'est la classe où permutationsDo: est défini et hérité, en fin de compte, par la classe Interval.

Catégorie "énumération":

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

Catégorie "privé":

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

Alors maintenant, vous pouvez faire:

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

Ce qui donne:

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

Ce sélecteur fonctionne de manière "symétrique" comme le sélecteur existant permutationsDo:, qui est le nombre d'éléments dans les tableaux résultants (le nombre de choix) est le même que le nombre de valeurs dans la collection.

---

Vous pouvez facilement passer de cela à une solution plus générale:

Sous "dénombrement":

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 ] 

Sous la rubrique "privée":

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

Voici un exemple:

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

Quels rendements:

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

Answer 2

Permettez-moi implémenter dans SequenceableCollection fo r Par souci de simplicité:

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 

L'idée est la suivante: Utilisez l'ordre lexicographique pour trier toutes les combinaisons. En d'autres termes:

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

si ai = bi pour tous i ci-dessous un indice j où aj < bj. Pour cette commande, la première combinaison est (0, ..., 0) et la dernière (9, ..., 9).

De plus, étant donné une combinaison (a1, ..., an) la suivante dans cet ordre est celui qui ajoute 1 au plus bas indice prééminent, c'est le dernier indice j où aj < 9. Par exemple le (2, 3, 8, 9) suivant est (2, 3, 9, 9) car il ne peut y avoir rien entre les deux. Une fois que nous arrivons à (9, ..., 9) nous avons terminé, et répondons par nil. Sachez que la méthode ci-dessus modifie le récepteur, ce qui explique pourquoi nous devons copy dans le script ci-dessous.

Voici le script qui produit toutes les combinaisons (n est votre N)

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

---

ADDENDA

La même technique peut être utilisée pour other problems de nature similaire.