Subj : Re: Unique sets from {1..n} ?
To   : comp.programming
From : cri
Date : Sat Jul 09 2005 05:18 pm

On 8 Jul 2005 00:29:21 -0700, "TC" <aatcbbtccctc@yahoo.com> wrote:

>Hi folks
>
>Apologies if this has been answered before. I've googled in various
>places & have not found it yet.
>
>I need to generate every unique set of numbers, of the integer numbers
>1 thru n inclusive.
>
>Eg. if n=3 (to take a small example), I need to generate the 7 unique
>sets:
>
>{1}  {2}  {3}  {1,2}  {2,3}  {1,3}  {1,2,3}
>
>Does anyone have a simple, doubtless recursive, pseudocode algorithym
>for this? I should be able to do it myself, but I seem to be having a
>dumb attack :-(


Whilst googling you might also look up generating gray code.  The
reason for this is that (using the binary mapping) each transition
from one subset to the next involves only a single change, either an
insertion or a deletion.  Thus:

Integer  Gray code  Subset
0        000        {}
1        001        {1}
2        011        {1,2}
3        010        {2}
4        110        {2,3}
5        111        {1,2,3}
6        101        {1,3}
7        100        {3}

There is a simple rule for generating gray code.  Perhaps you can
discover it.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

.