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

- Convert Sahni's solution to use iteration
- 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)

{

init(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 {

visit();

j = k;

// counter reached max limit, increase the

// counter next in the chain

while (j > 0 && (c[j] == ((n - k) + j))) {

j--;

uc = true;

}

if (j == 0) break;

c[j]++;

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] + " ");

Console.WriteLine();

}

// Find all subsets of a set

void subset(int n)

{

for (int i = 0; i <= n; i++) {

init(i);

combination(n, i);

}

}

public static void Main(string[] args)

{

int n;

if (args.Length != 1) {

Console.WriteLine("usage is subset");

return;

} else {

n = int.Parse(args[0]);

}

Combo p = new Combo(n);

p.subset(n);

}

}

## No comments:

Post a Comment