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


 

Forums >

comp.lang.ruby

TIMTOWTDI letter permutation

Endy Tjahjono

4/22/2005 3:32:00 AM

Hello all,

I have just created a function that returns all letter permutation in
a word, so if I put 'abc', it will return 'abc', 'acb', 'bac', 'bca',
'cab', 'cba'.

I want to know other ways to achieve the same result. Can you help?

Here's my code:

def geta(astr)
return [astr] if astr.length < 2

ret = []

0.upto(astr.length - 1) do |n|
rest = astr.split('')
picked = rest.delete_at(n)

geta(rest.join).each do |x|
ret << picked + x
end
end

ret
end

print "word: "
ainput = gets.chomp
puts geta(ainput)


BTW this post is inspired by the ruby quiz. Seeing the various ways
people solve the problems has been very educational. Too bad most of
the problems are too big for beginners like me to participate.

--
Endy
6 Answers

Paul Battley

4/22/2005 9:46:00 AM

0

I posted an Array permutation method to the RubyGarden wiki last year:
http://rubygarden.org/ruby?Ar...

It uses the same recursive method, although it yields a block for each
permutation rather than returning an array of permutations. Thanks to
your post, however, I have made a small improvement (the length < 2
test).

Paul.

Zed A. Shaw

4/22/2005 11:11:00 AM

0

On Fri, 2005-04-22 at 12:36 +0900, Endy Tjahjono wrote:
> Hello all,
>
> I have just created a function that returns all letter permutation in
> a word, so if I put 'abc', it will return 'abc', 'acb', 'bac', 'bca',
> 'cab', 'cba'.

You can use a suffix array to do this without recursion. See
http://www.cs.dartmouth.edu/~do... for an explanation.

I use a suffix array structure in fastcst but I haven't broken it out
yet. If you want to play with it, then contact me offline and I'll help
you get it configured.

zed

Zed A. Shaw

4/22/2005 11:13:00 AM

0

On Fri, 2005-04-22 at 12:36 +0900, Endy Tjahjono wrote:
> Hello all,
>
> I have just created a function that returns all letter permutation in
> a word, so if I put 'abc', it will return 'abc', 'acb', 'bac', 'bca',
> 'cab', 'cba'.

Oops, I mis-understood. I thought you wanted something different not
permutations. Ignore my last post.

Zed

Martin DeMello

4/26/2005 10:52:00 AM

0

Endy Tjahjono <endy_c@deadspam.com> wrote:
> Hello all,
>
> I have just created a function that returns all letter permutation in
> a word, so if I put 'abc', it will return 'abc', 'acb', 'bac', 'bca',
> 'cab', 'cba'.
>
> I want to know other ways to achieve the same result. Can you help?

Rather than just supply the solution, I'll provide a hint to get you
started. Consider the permutations of four letters:

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
....

Notice how the first 6 start with 'a', the next 6 with 'b', etc. Within
each block of 6, you have 2 permutations starting with each of the
remaining letters. You can generalise this pattern to directly calculate
the ith permutation of n letters, given n and i. Your generator then becomes

1..upto(n.factorial) {|i| puts permutation(n, i)}

with no recursion at all.

martin

Trans

4/28/2005 7:31:00 PM

0

Martin,

Don't leave us hang'n! What's this groovy i.th solution?

T.

William Morgan

4/28/2005 10:00:00 PM

0

Excerpts from Trans's mail of 28 Apr 2005 (EDT):
> Don't leave us hang'n! What's this groovy i.th solution?

The traditional solution breaks i into a sum of multiples of the
factorials of 1 to n-1 (the "pattern"), then successively pulls out
those multiples as indexes into the string.

Kinda hard to explain, but here's how you do it:

def permutation(s, i)
s = s.dup
pat = (1 .. s.length).map do |j|
r = i % j
i /= j
r
end
pat.reverse.map { |j| s.slice!(j).chr }.join
end

(Note that the first element of the pattern is always 0.)

--
William <wmorgan-ruby-talk@masanjin.net>