Subj : Re: how to generate a sequence?
To   : comp.programming
From : Neo
Date : Thu Sep 08 2005 07:27 pm

<gswork@mailcity.com> wrote in message 
news:1126182754.841342.319360@g44g2000cwa.googlegroups.com...
>
> Neo wrote:
>> Hi All,
>>
>> I have problem, I want to generate all possible (unique) combinations of 
>> the
>> following sequence:
>>
>>
>> 123456789
>> 213456789
>> 312456789
>> 321456789
>> .
>> .
>>
>>
>>
>> Symbols allowed : 1 - 9
>> Though, symbols can be anything like A B C D E F G H I, not necessarily
>> numbers.
>> NOTE: there will be !n (Factorial n) lines of output, 'coz there can be 
>> !n
>> combinations of n symbols.
>>
>>
>> Algo. required! Do U have a quick solution in mind???
>
> have you checked out any permutation algorithms?   source code is easy
> to find online.

Well, I first thought it will be a simple thing. when I give it a try, 
damm.. I was not able to devise an easy method to generate this sequence, 
this drives me crazy,  anyway then I decided to not do a google and attack 
it, after two hrs. I was able to come up with a solution (recursive). and 
just for the sake of watching things work, wrote  a quick script in PERL.

Well, for 4-5 symbols it was quick enough, but to ma surprise when I 
increase symbols to 9 damm.... it took 01 min 28.0954414 sec to exec    and 
it process's mem usage was 216 MB !!!!!!!!!!!!!!!!!!!!!


Here is my poor algo. .

SUBROUTINE PERMUTE(Set)
BEGIN
            resultSets = {}
            FOREACH ( currentSymbol IN Set )
            BEGIN
                        newSet = Set - currentSymbol    /*New set will be 
Set excluding current symbol*/
                        IF Length(newSet) > 1
                                    resultSetT = PERMUTE( newSet )
                                    FOREACH ( aSet IN resultSetT )
                                                Add currentSymbol in front 
of aSet
                                                resultSets += aSet
                        ELSE
                                    return { { currentSymbol, newSet[0]}, 
{ newSet[0], currentSymbol } }
                        ENDIF
            END
            return resultSets
END


NOTE:
A set can be e.g. {A, B}
{ {A,B,C}, {A,C,B} }  < -- is a set of sets.



BUT THIS IS REALY REALYYYYY CRAZY... This not absolutely not 
acceptable!!!!!!!
Think about this.. if this sequence is to be generated in an embedded system 
where maximum ram available is 32 KB only!!!!!!!!!!!

Regards,
-Neo

.