TIMTOWTDI letter permutation

[Endy Tjahjono]

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.

 

[Paul Battley]

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

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]

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/~doug/sarray/ 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]

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]

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]

Martin,

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

T.

 

[William Morgan]

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.)