From: Ken Bloom <kbloom@...>
Date: 2007-07-23T23:40:04+09:00
Subject: Re: array permutations

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

> Alex Ciarlillo 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.
>> 
>> 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
> 
> Have a look at this thread:
> 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.

There is a version of each_permutation in the Facets library (http://
facets.rubyforge.org/) which is similar to the version you posted. After 
relying on their version for several Ruby Quizzes, 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

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/