Last time I showed how to use an immutable stack of Booleans to act as flags indicating whether a particular element of a sequence should be chosen as one of the combinations of exactly k elements. A reasonable criticism of this approach is that when you have a stack containing, say, thirty flags, each of which is a managed object and contains a Boolean and a reference, then we’ve overspent by a large factor; thirty bits could fit into a single int.

Now, on the one hand, who the heck cares whether we use 4 bytes per bit stack or 400 for this problem? The lowest common denominator 32 bit machine has two billion bytes of address space, and it seems unlikely that the difference between success and failure in the market is going to be the difference between 4 bytes and 400 bytes.

On the other hand, representing a combination in a single int is an interesting challenge and lets me demonstrate a nice variant of the algorithm I presented last time. (Incidentally, an alert reader pointed out a harmless but vexing bug in my algorithm of last time, which I have fixed; see the post for details.)

Last time we used an immutable stack of Booleans; this time we’re going to use an immutable set of integers. (Recall that a set is a collection which has no particular order imposed on its elements, and there are no duplicate elements.) Our immutable stack was designed so that pushing did not mutate the stack; rather, it produced a new stack with the pushed element on it. Similarly, our immutable set will have an “add” method that does not mutate the set; rather, it returns a new set with the item added. We’ll make this set a struct so that it really does consume no more memory than its single int field:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

internal struct TinySet : IEnumerable<int>
{
  public static readonly TinySet Empty = new TinySet(0);
  public const int Minimum = 0;
  public const int Maximum = 31;
  private readonly int bits;
  private TinySet(int bits) { this.bits = bits; }
  public bool Contains(int item) 
  {
    if (item < Minimum || item > Maximum) 
      return false;
    return (bits & (1 << item)) != 0; 
  }
  public TinySet Add(int item) 
  { 
    if (item < Minimum || item > Maximum)
      throw new InvalidOperationException();
    return new TinySet(bits | (1 << item)); 
  }
  public TinySet Remove(int item) 
  { 
    if (item < Minimum || item > Maximum)
      return this;
    return new TinySet(bits & ~(1 << item)); 
  }
  IEnumerator IEnumerable.GetEnumerator() 
  { 
    return this.GetEnumerator(); 
  }
  public IEnumerator<int> GetEnumerator()
  {
    for(int item = Minimum; item <= Maximum; ++item)
      if (Contains(item))
        yield return item;
  }
}

Long time readers will recognize this as the same tiny set I used in my series on graph colouring. We’re not going to need removal but I added it anyways just for the heck of it. Adding other features like union, intersection, and so on, is easily done and left for the reader.

We can then use this set the same way we used our stack; the code

TinySet mySet = TinySet.Empty.Add(1).Add(0).Add(3);

produces the set {0, 1, 3}.

Next time: Now that we have this data structure we can modify our algorithm of last time to produce all the combinations.