Figures

Combinations

static void Main()
{
  long n = 4;
  long k = 2;
  Console.WriteLine("With n = " + n + ", and k = " + k);
  Console.WriteLine("There are " + Combination.Choose(n,k) + 
      "combinations\n");

  Combination c = new Combination(n,k);
  Console.WriteLine("The mathematical combinations are:");
  while (c != null)
  {
    Console.WriteLine(c.ToString());
    c = c.Successor();
  }
  Console.ReadLine();
}

---

Combination Class Definition

public class Combination
{
  private long n = 0;
  private long k = 0;
  private long[] data = null;

  public Combination(long n, long k)
  {
    if (n < 0 || k < 0) // normally n >= k
      throw new Exception("Negative parameter in constructor");  
    this.n = n;
    this.k = k;
    this.data = new long[k];
    for (long i = 0; i < k; ++i)
      this.data[i] = i;
  }

  public override string ToString()
  {
    StringBuilder sb = new StringBuilder();
    sb.Append("{ ");
    for (long i = 0; i < this.k; ++i)
      sb.AppendFormat("{0} ", this.data[i]);
    sb.Append("}");
    return sb.ToString;
  }

---

Efficient Choose Method Implementation

public static long Choose(long n, long k)
{
  if (n < 0 || k < 0)
    throw new Exception("Invalid negative parameter in Choose()"); 
  if (n < k) return 0;
  if (n == k) return 1;

  long delta, iMax;

  if (k < n-k) // ex: Choose(100,3)
  {
    delta = n-k;
    iMax = k;
  }
  else         // ex: Choose(100,97)
  {
    delta = k;
    iMax = n-k;
  }

  long ans = delta + 1;

  for (long i = 2; i <= iMax; ++i)
  {
    checked { ans = (ans * (delta + i)) / i; } 
  }

  return ans;
}

---

Lexicographic Successor of an Element

public Combination Successor()
{
  if (this.data.Length == 0 ||
      this.data[0] == this.n - this.k)
    return null;

  Combination ans = new Combination(this.n, this.k);

  long i;
  for (i = 0; i < this.k; ++i)
    ans.data[i] = this.data[i];
 
  for (i = this.k - 1; i > 0 && ans.data[i] == this.n - this.k + i; 梚) ;
 
  ++ans.data[i];

  for (long j = i; j < this.k - 1; ++j)
    ans.data[j+1] = ans.data[j] + 1;

  return ans;
}

---

--------------------next---------------------