From: Rob Biedenharn <Rob@...>
Date: 2006-08-01T10:35:34+09:00
Subject: Re: Array#permutate

You could look at http://permutation.rubyforge.org/

Rob Biedenharn		http://agileconsultingllc.com
Rob@AgileConsultingLLC.com


On Jul 31, 2006, at 7:29 AM, Daniel Martin wrote:

> Sch�le Daniel <uval@rz.uni-karlsruhe.de> writes:
>
>> Hello,
>>
>> this is my handmade Array#permutate function
>> are there any alternatives (maybe C extension modules)?
>> especially are there functions that would not create all
>> permutations and return them as one single memory consuming array
>> but give each one on demand?
>
> Well, aside from using a better algorithm (e.g. Djikstra's), we can
> easily take your algorithm, and modify it to yield each array as it
> discovers it (I've removed the size 2 and 3 base cases since they
> aren't needed).
>
> class Array
>   # "permutate" ist kein englishes Wort
>   def each_permutation
>     if (size < 2)
>       yield self
>       1
>     else
>       first_array = [ self[0] ]
>       self[1..-1].each_permutation {|r|
>         size.times {|pos|
>           yield(r[0...pos] + first_array + r[pos..-1])
>         }
>       } * size
>     end
>   end
> end
>
> As a bonus, the return value of each_permutation is the number of
> permutations:
>
> irb(main):120:0> [1,2,3,4].each_permutation {|c| p c}
> [1, 2, 3, 4]
> [2, 1, 3, 4]
> [2, 3, 1, 4]
> [2, 3, 4, 1]
> [1, 3, 2, 4]
> [3, 1, 2, 4]
> [3, 2, 1, 4]
> [3, 2, 4, 1]
> [1, 3, 4, 2]
> [3, 1, 4, 2]
> [3, 4, 1, 2]
> [3, 4, 2, 1]
> [1, 2, 4, 3]
> [2, 1, 4, 3]
> [2, 4, 1, 3]
> [2, 4, 3, 1]
> [1, 4, 2, 3]
> [4, 1, 2, 3]
> [4, 2, 1, 3]
> [4, 2, 3, 1]
> [1, 4, 3, 2]
> [4, 1, 3, 2]
> [4, 3, 1, 2]
> [4, 3, 2, 1]
> => 24
>
>