## 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)  {  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);  }  Combo p = new Combo(n);  p.subset(n);   }}

### 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'...