Генерация всех комбинаций из коллекций в Smalltalk - PullRequest
Новая
       37

Генерация всех комбинаций из коллекций в Smalltalk

2 голосов
/ 26 марта 2012

Я видел, что эта проблема решена для C # и других языков, но не для Smalltalk.У меня есть 3 коллекции, например: 

a := #(3 4 5).
b := #(4 1 2).
c := #(5 2 3).

, и мне нужно сделать все возможные комбинации, например: 

#(3 4 5)
#(3 4 2)
#(3 4 3)

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

#(3 2 5)
#(3 2 2)
#(3 2 3)

#(4 4 5)
...

Я видел, что в Squeak и Pharo есть комбинации: atATimeDo:но я не понимаю, как использовать это для этого случая.Это не домашнее задание.Любая помощь?

Ответы [ 3 ]

3 голосов
/ 26 марта 2012

Это немного загадочно, но коротко.Он использует блок как анонимную функцию (вроде как, на него все равно нужно ссылаться из переменной, чтобы его можно было вызывать рекурсивно). 

| expand |
expand := [ :prefix :lists |
    lists isEmpty
        ifTrue: [ Array with: prefix ]
        ifFalse: [ | tail |
            tail := lists allButFirst: 1.
            lists first inject: #() into: [ :all :each |
                all, (expand value: (prefix copyWith: each) value: tail) ] ] ].
expand value: #() value: #((3 4 5)(4 1 2)(5 2 3))
2 голосов
/ 26 марта 2012

вот код из библиотеки классов Smalltalk / X (в SequentialCollection). См. Пример - используйте комментарии в конце. 

combinationsDo: aBlock
    "Repeatly evaluate aBlock with all combinations of elements from the receivers elements. 
     The receivers elements must be collections of the individuals to be taken for the combinations"

    self combinationsStartingAt:1 prefix:#() do:aBlock

combinationsStartingAt:anInteger prefix:prefix do:aBlock
    "a helper for combinationsDo:"

    |loopedElement|

    loopedElement := self at:anInteger.

    anInteger == self size ifTrue:[
        loopedElement do:[:el | aBlock value:(prefix copyWith:el)].
        ^ self.
    ].

    loopedElement do:[:el |
        |newPrefix|

        newPrefix := (prefix copyWith:el).
        self combinationsStartingAt:anInteger+1 prefix:newPrefix do:aBlock
    ].

    "
     (Array 
            with:($a to:$d)
            with:(1 to: 4)) 
        combinationsDo:[:eachCombination | Transcript showCR: eachCombination]
    "
    "
     (Array 
            with:#(1 2 3 4 5 6 7 8 9)
            with:#(A)) 
        combinationsDo:[:eachCombination | Transcript showCR: eachCombination]
    "
    "
     #( (3 4 5) 
        (4 1 2)
        (5 2 3) 
     ) combinationsDo:[:eachCombination | Transcript showCR: eachCombination]
    "
1 голос
/ 04 июня 2012

Цель комбинаций: atATimeDo: состоит в том, чтобы вычислить разделы заданного размера.
Чтобы получить декартово произведение, рекурсивная функциональная версия, предоставленная Мартином Кобетиком, является самым коротким кодом.
Вот итерационный вариант:

| arrayOfArray n p cartesianProduct |
arrayOfArray := #(
    #(3 4 5)
    #(4 1 2)
    #(5 2 3)
).
n := arrayOfArray size.
p := arrayOfArray inject: 1 into: [:product :array | product * array size].
cartesianProduct := (Array new: p) collect: [:i | Array new: n].
1 to: p do: 
    [:iSol | 
    | packetIndex |
    packetIndex := iSol - 1.
    n to: 1 by: -1 do: 
        [:iVar | 
        | ni valuesOfIVar |
        ni := (valuesOfIVar := arrayOfArray at: iVar) size.
        (cartesianProduct at: iSol)
            at: iVar put: (valuesOfIVar at: packetIndex \\ ni + 1).
        packetIndex := packetIndex // ni]].
^cartesianProduct
...