Array#permutate

ruby-talk
1

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?

Regards, Daniel

# arrayperm.rb

class Array
         def permutate
                 return self if [0,1].member? size
                 return [self, self.reverse] if size == 2
                 return [[self[0],self[1],self[2]],
                          [self[0],self[2],self[1]],
                          [self[1],self[0],self[2]],
                          [self[1],self[2],self[0]],
                          [self[2],self[0],self[1]],
                          [self[2],self[1],self[0]]] if size == 3
                 ret = []
                 for perm in self[1..-1].permutate
                         for i in 0..perm.size
                                 ret.push( perm[0...i] + [first] + perm[i..-1] )
                         end
                 end
                 return ret
         end
end

irb(main):011:0* require "arrayperm"
=> true
irb(main):012:0> [1,2,3,4].permutate.size
=> 24
irb(main):013:0> [1,2,3,4].permutate.each{|perm| p perm};nil
[1, 2, 3, 4]
[2, 1, 3, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[1, 2, 4, 3]
[2, 1, 4, 3]
[2, 4, 1, 3]
[2, 4, 3, 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, 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]
=> nil
irb(main):014:0>

2

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

4

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