Subj : Re: Unique sets from {1..n} ?
To   : comp.programming
From : Willem
Date : Fri Jul 08 2005 10:37 am

TC 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}

There are *eight* unique sets, you forgot the empty set.

Try to work out how many sets there are for n=2, n=4, n=5 and see if
you can spot the pattern.

Or, alternatively, write out the subsets in a list, top to bottom,
putting all the ones in a column, all the twos in another column,
and so on.  See the pattern now ?

) 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 :-(

If you're making a subset, each number in the range either is or isn't
in that subset.  So, to create a subset, you have to answer N yes/no
questions (is number n in the subset ?).  Still dont see the pattern ?


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.