From: Daniel Martin <martin@...>
Date: 2006-07-31T20:29:25+09:00
Subject: Re: Array#permutate

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