Creating all subsets recursively without using array

Question

We get non negative integer number n from user and we must print all subsets of set ({1,2,3,...,n}). (n<=20)

for example for n=3 we must print:

{1 , 2 , 3}
{1 , 2}
{1 , 3}
{1}
{2 , 3}
{2}
{3}
{}

,s are optional and the sequence can be printed without any comma. (like {1 2 3}) I must add that the sequence of subsets must be exactly like the example. Meaning first the subsets that have 1, then subsets that have 2 and .... The longest subset must be printed first. (lexicographical from the largest subset (the set itself) to null set)

I see a lot of codes in the Internet that solve this problem with arrays or using a bit array that indicate whether we use a number or not. The issue is that in this question, we are not allowed to use -any- type of array or other data structures like vector ,etc. Even using the array behaviour of something like string is completely prohibited. It must be solved only with recursion.

We are also not allowed to use any advanced functions. For example if we write it with C, we are allowed just to use stdio.h or for C++, only <iostream> is allowed and no other library.

I don't know how to do this without any arrays. How to check which number it must print and at the sametime, manage the {}.

PS1. The question is simply generation powerset with these conditions:

USING ARRAY, STRING AND EVEN LOOPS ARE COMPLETELY PROHIBITED. JUST RECURSION.

User Kosyr submitted a very good answer with bit operators. So if you want to submit another answer, submit an answer that even doesn't use bit operators.

PS2.

I write this code by help of George but it doesn't works fine. It doesn't have something like 1 2 4. It also repeats some cases.

#include <stdio.h>


void printAllSets (int size)
  {printRows (size, 1);}

void printRows (int size , int start)
{
  if (start<=size)
  {printf( "{ ");
  printRow (start, size);
  printf ("}");
  printf ("\n");}
  if (start <= size)
  {printRows(size -1 , start);
    printRows (size , (start + 1));}
}
printRow (int start, int limit)
{

  if (start <= limit)
  {

    printf ("%d ",start);
    printRow (start +1, limit);
  }
}


int main()
{
    printAllSets(5);
    printf("{ }");
    return 0;
}

PS3.

User Kosyr submitted a very good answer with bit operators. So if you want to submit another answer, submit an answer that even doesn't use bit operators.

Answer 1

By definition, the powerset of a set k, powerset k, is the set of all possible sets containing elements from that given set including the empty set itself. Clearly, when k is the empty set powerset [] is simply the set containing the empty set, [ [] ]. Now, given a power set of k, powerset k, the powerset for k plus an additional element, E, powerset (K+E), would include all possible sets containing elements without E, powerset k, plus those same elements except now all containing E

pseudo code...

let powerset k =
   match k with
   | [] -> [[]]
   | x:xs -> x * powerset xs + powerset xs

or with tail call equivalent performance

let powerset k =
   let (*) e ess = map (es -> e::es) ess
   reduce (e ess -> (e * ess) ++ ess) [ [] ] (reverse k)

....(In F#)

let rec powerset k =
  match k with
  | []    -> [ [] ]
  | x::xs -> 
      let withoutE = powerset xs
      let withE = List.map (fun es -> x::es) withoutE
      List.append withE withoutE

or more succinctly

let rec powerset = function
  | []    -> [ [] ]
  | x::xs -> List.append (List.map (fun es -> x::es) (powerset xs)) (powerset xs)

A better version would allow for tail call optimization...which we achieved using common functional patterns:

let rec powerset2 k = 
  let inline (++) a b = List.concat [a;b]
  let inline (+*) a bs = List.map (fun b -> a::b) bs
  List.fold 
    (fun ac a -> (a +* ac) ++ ac)
    [ [] ] 
    (List.rev k)

-- this all took me a while to rediscover. It was a fun little puzzle. :)

Answer 2

I think we can solve this iteratively, which we can assume could also be converted to recursion, although it seems unnecessary. Consider that we can unrank any of the combinations given its index, using common knowledge. So all we need to do is count how many earlier combinations we are skipping and how many we need to unrank at each stage of the iteration (I may have missed something in the following but I think the general idea is sound):

Skip 0, unrank from `3 choose 3`
`2 choose 2` combinations
{1 , 2 , 3} 

Skip 0, unrank from `3 choose 2`
`2 choose 1` combinations
{1 , 2}
{1 , 3}

Skip 0, unrank from `3 choose 1`
`2 choose 0` combinations
{1}

Skip `3 choose 2 - 2 choose 2`,
unrank from `3 choose 2`
`1 choose 1` combinations
{2 , 3}

Skip `3 choose 1 - 2 choose 1`,
unrank from `3 choose 1`
`1 choose 0` combinations
{2}

Skip `3 choose 1 - 1 choose 1`,
unrank from `3 choose 1`
`0 choose 0` combinations
{3}

Empty set
{}

Answer 3

Recursive algorithms are very memory intensive. Here algorithm for n <= 31

#include <iostream>

void bin(unsigned bit, unsigned k, unsigned max_bits) {
    if (bit == max_bits) {
        std::cout << "{";
        bin(bit - 1, k, max_bits);
    }
    else {
        if ((k & (1u << bit)) != 0) {
            std::cout << (max_bits - bit) << " ";
        }
        if (bit != 0) {
            bin(bit - 1, k, max_bits);
        }
        else {
            std::cout << "}" << std::endl;
        }
    }
}

void print(unsigned k, unsigned n, unsigned max_bits) {
    bin(max_bits, k, max_bits);
    if (k != 0) {
        print(k - 1, n, max_bits);
    }
}

int main()
{
    unsigned n;
    std::cin >> n;
    print((1u << n) - 1u, 1u<<n, n);
    return 0;
}

First recursion print enumerates k from 2^n-1 to 0, second recursion bin enumerates all bits of k and print non-zero bits. For example, max_bits = 5 and k = 19 is 10011b = 16 + 2 + 1 = 2^4 + 2^1 + 2^0, bits 4,1,0 interoperate as set {5-4,5-1,5-0} => {1,4,5}

Answer 4

The alternative to loops is recursion.

To solve this problem (I think...haven't tested it), I investigate the problem by tabulating the sample date and discerned three states, Size, Start, and Limit with progression as follows:

Size  Start Limit   Output
  10      1    10    1..10
  10      1     9     1..9
              ...      ...
  10      1     1        1
  10      2    10    2..10
  10      2     9     2..9
              ...      ...
  10      2     2        2
        ...   ...      ...
  10     10    10       10

The following recursive algorithm in pseudo code may do the trick:

printAllSets size
  printRows size 1

printRows size start
  print "{"
  printRow start size
  print "}"
  print CRLF
  if start <= size
    printRows size (start + 1)

printRow start limit
  if start <= limit
    print start + SPACE
    printRow start (limit - 1)

Hope this at least helps point you in the right direction.