Subj : Re: Unique sets from {1..n} ?
To   : comp.programming
From : Dave Seaman
Date : Fri Jul 08 2005 02:08 pm

On Fri, 8 Jul 2005 09:37:08 +0000 (UTC), Willem wrote:
> 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

If S is empty, return {{}} and you are done.  

Otherwise, choose s in S and let S' = S \ {s} (S with one element
removed).  Let T = P(S'), applying the powerset algorithm recursively.

For each set in T you need two sets in P(S):  one with the element
s appended, and one without.

Done.

In Python:

def P(S):
  if len(S) == 0: return [[]]
  s = S[-1]
  T = P(S[:-1])
  res = T[:]
  for t in T:
    res.append(t + [s])
  return res

.