12/05/03 20:11:32.07
>>653 も書いてみた。これも重複要素があるとバグる。
SequenceableCollection >> perm
self size < 1 ifTrue: [^Array with: self].
^self inject: #() into: [:r1 :n |
(self reject: [:x | x = n]) perm inject: r1 into: [:r2 :ary |
r2 copyWith: (ary copyWithFirst: n)]]
#(1 2 3) perm "=> #((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) "
ちなみに、Squeak Smalltalkで組み込みのpermutation相当を見たらこんなふうに
破壊的操作による実装だった。
class Array
def perm_each(&block)
clone.perm_start_at(0, &block)
end
def perm_start_at(n, &block)
return if n > size-1
return block.call(self) if n == size-1
(n..size-1).each do |i|
swap!(n, i)
perm_start_at(n+1, &block)
swap!(n, i)
end
end
def swap!(a, b); self[a], self[b] = self[b], self[a] end
end