From: Martin DeMello <martindemello@...>
Date: 2005-04-26T19:54:30+09:00
Subject: Re: TIMTOWTDI letter permutation

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