# Array#permutate

**URL:** <https://www.ruby-forum.com/t/array-permutate/100628>\
**Category:** Ruby\
**Created:** [July 31, 2006, 1:12am UTC](https://www.ruby-forum.com/t/array-permutate/100628 "2006-07-31T01:12:48Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![SchSSS\_le\_Daniel](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/a183cd/32.png) [@SchSSS\_le\_Daniel](https://www.ruby-forum.com/u/SchSSS_le_Daniel)\
**Post date:** [July 31, 2006, 1:12am UTC](https://www.ruby-forum.com/t/array-permutate/100628/1 "2006-07-31T01:12:48Z")

</div>

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\>

---

<div class="post-metadata">

**Author:** ![SchSSS\_le\_Daniel](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/a183cd/32.png) [@SchSSS\_le\_Daniel](https://www.ruby-forum.com/u/SchSSS_le_Daniel)\
**Post date:** [July 31, 2006, 1:31pm UTC](https://www.ruby-forum.com/t/array-permutate/100628/2 "2006-07-31T13:31:10Z")

</div>

Schüle Daniel [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![SchSSS\_le\_Daniel](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/a183cd/32.png) [@SchSSS\_le\_Daniel](https://www.ruby-forum.com/u/SchSSS_le_Daniel)\
**Post date:** [August 1, 2006, 3:38am UTC](https://www.ruby-forum.com/t/array-permutate/100628/3 "2006-08-01T03:38:37Z")

</div>

You could look at [http://permutation.rubyforge.org/](http://permutation.rubyforge.org/)

Rob B. [http://agileconsultingllc.com](http://agileconsultingllc.com)  
removed\_email\_address@domain.invalid