TIMTOWTDI letter permutation

ruby-talk
1

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

2

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.

3

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

···

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

4

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

Zed

···

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

5

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

···

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?

6

Martin,

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

T.

7

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>