Subj : Re: how to generate a sequence?
To   : comp.programming
From : Rob Thorpe
Date : Thu Sep 08 2005 08:16 am

gswork@mailcity.com wrote:
> Neo wrote:
>
> > <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 ...
> > >
> > > 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 !!!!!!!!!!!!!!!!!!!!!
>
> that'll be the recursion.   A non recursive permutation algorithm would
> help you for the constrained environment you mention (the 32kb one)

It's not the recusion per se but rather the fact that the local
variables in the recursive function shown contain a lot of data that
make the method shown use so much memory.  It would probably still use
more that 32kB if it were done with recursion in another way (assuming
it's not tail-recursion).

> it would involve swapping elements in the set in an iterative process
> but exactly how got me thinking - so I looked around - indeed there was
> a website all about it!  (http://www.geocities.com/permute_it/)

There is an entire chapter of Knuths as-yet-unfinished 4th volume of
TAOCP on the subject.  See
http://www-cs-faculty.stanford.edu/~knuth/taocp.html, this is complex
and through of course - I haven't read it.  It's also covered briefly
in vol2.

Also, there is a non-recursive algorithm given here:
http://groups.google.co.uk/group/comp.lang.c/msg/39adb72a8c62827f?hl=en&

.