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
···
--
Posted via http://www.ruby-forum.com/.
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.
Have fun,
Dan
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
···
2007/7/23, Alex Ciarlillo <ac251404@ohio.edu>:
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
--
Posted via http://www.ruby-forum.com/\.
The one thing I learned in Algs is someone has invented/implemented/tested it before me:
http://rubygarden.org/Ruby/page/show/ArrayPermute
Please use google.
···
On Jul 22, 2007, at 21:52 , 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.
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
···
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.
--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/