Thursday, March 31, 2005

Subsets of a given set

I read this interesting problem in Sahni, the problem is to generate all given subsets of a set. Sahni's answer is given on the web site at solution to exercise 5. I tried to solve the problem using iteration. There are two ways to do it

  1. Convert Sahni's solution to use iteration
  2. Use the method I describe (its a bit complex, but interesting)

The solution described in (1) eventually ends up generating all possible binary numbers for a word of length n. Where n is the number of elements in the set. This method will definitely not work for multisets. I solved the problem by first coming up with a method to generate combinations of C(n, k) which prints out all combinations of n taken k at a time. I have the C# implementation of the code, if you want to see it, let me know. This method can be easily extended to handle multisets (I think!)

Here is my implementation

// I am not an expert C# programmer,
// I am learning the language please
// feel free to comment on the style
// and/or on the code
using System;

class Combo

int[] c; // counter for holding c1 .. ck
int k; // k of C(n, k)

Combo(int k)

// For C(n, k), call it with k
void init(int k)
c = new int[k+1];
for (int i = 0; i <= k; i++)
c[i] = i;
this.k = k;

// prints all combinations of C(n, k)
// assuming they are in lexicographic
// order
void combination(int n, int k)
int j;
bool uc = false;

do {
j = k;
// counter reached max limit, increase the
// counter next in the chain
while (j > 0 && (c[j] == ((n - k) + j))) {
uc = true;
if (j == 0) break;
if (uc) {
// reload counters
for (int i = j+1, l = 1; i <= k; i++, l++)
c[i] = c[j]+l;
uc = false;
} while (true);

void visit()
for (int i = 1; i <= k; i++)
Console.Write(c[i] + " ");

// Find all subsets of a set
void subset(int n)
for (int i = 0; i <= n; i++) {
combination(n, i);

public static void Main(string[] args)
int n;
if (args.Length != 1) {
Console.WriteLine("usage is subset ");
} else {
n = int.Parse(args[0]);

Combo p = new Combo(n);


No comments:

Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...