# Array permutations

**URL:** <https://www.ruby-forum.com/t/array-permutations/110101>\
**Category:** Ruby\
**Created:** [July 23, 2007, 6:51am UTC](https://www.ruby-forum.com/t/array-permutations/110101 "2007-07-23T06:51:29Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![combas](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/aca169/32.png) [@combas](https://www.ruby-forum.com/u/combas)\
**Post date:** [July 23, 2007, 6:51am UTC](https://www.ruby-forum.com/t/array-permutations/110101/1 "2007-07-23T06:51:29Z")

</div>

The other day I ran into a problem where I needed all the permutations  
of a given array. I knew I had covered this in some of my CS classes but  
couldn’t come up with the algorithm at first. I figured it out on the  
drive home from work and decided to rubify it and add it as a method to  
the array class. This is what I came up with and was just wondering if  
anyone else had a cleaner or more effecient way of accomplishing this.

class Array  
def each\_perm  
if self.size == 1  
yield self  
else  
self.each\_index do |i|  
tmp, e = self.dup, self[i]  
tmp.delete\_at(i)  
tmp.each\_perm do |x|  
yield e.to\_a + x  
end  
end  
end  
end  
end

–AC

---

<div class="post-metadata">

**Author:** ![combas](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/aca169/32.png) [@combas](https://www.ruby-forum.com/u/combas)\
**Post date:** [July 23, 2007, 8:37am UTC](https://www.ruby-forum.com/t/array-permutations/110101/2 "2007-07-23T08:37:10Z")

</div>

Alex C. wrote:

> ```
> yield self
> 
> ```
> 
> end
> 
> –AC

Have a look at this thread:  
[http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/247669](http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/247669) .  
It’s a port of the GCC library version to ruby. As for efficiency,  
you’ll have to run them both (I haven’t read either version carefully).  
One factor that might make his slower is that it should avoids yielding  
duplicates.

Have fun,  
Dan

---

<div class="post-metadata">

**Author:** ![combas](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/aca169/32.png) [@combas](https://www.ruby-forum.com/u/combas)\
**Post date:** [July 23, 2007, 8:44am UTC](https://www.ruby-forum.com/t/array-permutations/110101/3 "2007-07-23T08:44:27Z")

</div>

2007/7/23, Alex C. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> ```
> if self.size == 1
> 
> ```
> 
> end  
> end
> 
> ## –AC
> 
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

There’s a problem with the “to\_a” in “yield e.to\_a + x”. It gets a lot  
of  
“default `to\_a’ will be obsolete” warnings, and it gives the wrong  
result  
for, for instance, [1, 2, ‘a’…‘z’].each\_perm. I’d go with “yield [e] +  
x”  
instead.

For the rest, looks OK to me.

Regards,  
Raf

---

<div class="post-metadata">

**Author:** ![combas](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/aca169/32.png) [@combas](https://www.ruby-forum.com/u/combas)\
**Post date:** [July 26, 2007, 12:45am UTC](https://www.ruby-forum.com/t/array-permutations/110101/4 "2007-07-26T00:45:48Z")

</div>

On Mon, 23 Jul 2007 15:36:24 +0900, Dan Z. wrote:

> > def each\_perm  
> > end  
> > One factor that might make his slower is that it should avoids yielding  
> > duplicates.

There is a version of each\_permutation in the Facets library (http://  
[facets.rubyforge.org/](http://facets.rubyforge.org/)) which is similar to the version you posted. After  
relying on their version for several Ruby Q.zes, I decided that it  
wasn’t as useful to me as I would have liked, because I found I had to  
do  
bookkeeping for duplicates anyway, so I ported over the C++ STL version  
which doesn’t generate duplicates (because it’s stateless).

Different design goals.

–Ken

---

<div class="post-metadata">

**Author:** ![combas](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/aca169/32.png) [@combas](https://www.ruby-forum.com/u/combas)\
**Post date:** [July 23, 2007, 8:49am UTC](https://www.ruby-forum.com/t/array-permutations/110101/5 "2007-07-23T08:49:37Z")

</div>

On Jul 22, 2007, at 21:52 , Alex C. wrote:

> The other day I ran into a problem where I needed all the permutations  
> of a given array. I knew I had covered this in some of my CS  
> classes but  
> couldn’t come up with the algorithm at first. I figured it out on the  
> drive home from work and decided to rubify it and add it as a  
> method to  
> the array class. This is what I came up with and was just wondering if  
> anyone else had a cleaner or more effecient way of accomplishing this.

The one thing I learned in Algs is someone has invented/implemented/  
tested it before me:

[http://rubygarden.org/Ruby/page/show/ArrayPermute](http://rubygarden.org/Ruby/page/show/ArrayPermute)

Please use google.