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);
}
}
