Array#permutate

[Schüle Daniel]

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>

 

[Daniel Martin]

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 =3D [ 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]
=3D> 24

 

[Rob Biedenharn]

 

[Rob Biedenharn]

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

Rob Biedenharn http://agileconsultingllc.com
(e-mail address removed)

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 =3D [ 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]
=3D> 24