Array#permutate

Ruby
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 [email protected] 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

3

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

Rob B. http://agileconsultingllc.com
[email protected]