[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Array#permutate

Daniel Schüle

7/30/2006 11:07:00 PM

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>
4 Answers

Daniel Martin

7/31/2006 11:29:00 AM

0

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

Jeff Schwab

7/31/2006 10:19:00 PM

0

Schüle Daniel wrote:

> this is my handmade Array#permutate function

You might want to look at an existing permutation package. Run:

gem install permutation

And please, for the love of God, rename your function from "permutate"
to "permute."

Rob Biedenharn

8/1/2006 1:22:00 AM

0



Rob Biedenharn

8/1/2006 1:36:00 AM

0

You could look at http://permutation.ruby...

Rob Biedenharn http://agileconsult...
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
>
>