Generalizing the Poker Coder into a combinatorial series coder...
Two reasons for this really. First, I promised I'd do something with formalizing the code originated by Tim when I originally posed the problem. Second, a reader has had some issues downloading the original zip file. Since we have the opportunity we'll increase the original problem to coding any series where we know the range and the number of elements we'll be encoding. If you need to code an arbitrary number of elements in a range then you'd have to add additional support for that.
public static int[] DecodeSeries(int code, int minValue, int maxValue, int length) {
int[] decode = new int[length];
int range = maxValue - minValue;
int lastValue = 0;
for(int i = 0; i < length; i++) {
for(int j = lastValue;;j++) {
int coefficient = BinomialCoefficient(range - j, length - i - 1);
if ( coefficient > code ) {
decode[i] = j + minValue;
lastValue = j + 1;
break;
}
code -= coefficient;
}
}
return decode;
}
public static int EncodeSeries(int[] series, int minValue, int maxValue) {
int encoding = 0;
int range = maxValue - minValue;
int lastValue = 0;
for(int i = 0; i < series.Length; i++) {
for(int j = lastValue; j < series[i] - minValue; j++) {
encoding += BinomialCoefficient(range - j, series.Length - i - 1);
}
lastValue = series[i] - minValue + 1;
}
return encoding;
}
public static int BinomialCoefficient(int n, int k) {
int numerator = 1;
int denominator = 1;
for (int p=0; p<k; p++) {
numerator *= (n-p);
denominator *= (p+1);
}
return numerator/denominator;
}
Sorry, no time for huge explanations, but hopefully the code is quite usable and self-explanatory. I think discovering code through it's output is important and so I'll also give you two test programs that help to verify the output of the methods. The first set of tests handles the poker hands by verifying the uniqueness during the encoding process, that the decoding process works correctly, and shows one way of calling the methods.
int items = 52; int selections = 5;
int[] tenFive = new int[BinomialCoefficient(items, selections)];
for(int i = 0; i < items - 4; i++) {
for(int j = i + 1; j < items - 3; j++) {
for(int k = j + 1; k < items - 2; k++) {
for(int l = k + 1; l < items - 1; l++) {
for(int m = l + 1; m < items; m++) {
int encode = EncodeSeries(new int[] { i, j, k, l, m }, 0, items - 1);
int[] decode = DecodeSeries(encode, 0, items - 1, 5);
tenFive[encode]++;
#if DEBUG
Console.WriteLine("{0}, {1}, {2}, {3}, {4}",
decode[0], decode[1], decode[2], decode[3], decode[4] );
#endif
if ( i != decode[0] ) { Console.WriteLine("Failure"); }
if ( j != decode[1] ) { Console.WriteLine("Failure"); }
if ( k != decode[2] ) { Console.WriteLine("Failure"); }
if ( l != decode[3] ) { Console.WriteLine("Failure"); }
if ( m != decode[4] ) { Console.WriteLine("Failure"); }
}
}
}
}
}
Console.WriteLine("Verifying {0} combinations", tenFive.Length);
for(int i = 0; i < tenFive.Length; i++) {
if ( tenFive[i] != 1 ) {
Console.WriteLine("Failure");
return;
}
}
}
That isn't a very interesting combination though. We've done the poker deck already and it was fun. Other series may be important as well. We can encode a series of numbers in the range of -10 to +10 using a slight variation.
int low = -10; int high = 10;
int selections = 5;
int[] tenFive = new int[BinomialCoefficient(high - low + 1, selections)];
for(int i = low; i < high + 5; i++) {
for(int j = i + 1; j < high + 4; j++) {
for(int k = j + 1; k < high + 3; k++) {
for(int l = k + 1; l < high + 2; l++) {
for(int m = l + 1; m < high + 1; m++) {
int encode = EncodeSeries(new int[] { i, j, k, l, m }, low, high);
int[] decode = DecodeSeries(encode, low, high, 5);
tenFive[encode]++;
if ( i != decode[0] ) { Console.WriteLine("Failure"); }
if ( j != decode[1] ) { Console.WriteLine("Failure"); }
if ( k != decode[2] ) { Console.WriteLine("Failure"); }
if ( l != decode[3] ) { Console.WriteLine("Failure"); }
if ( m != decode[4] ) { Console.WriteLine("Failure"); }
}
}
}
}
}
Console.WriteLine("Verifying {0} combinations", tenFive.Length);
for(int i = 0; i < tenFive.Length; i++) {
if ( tenFive[i] != 1 ) {
Console.WriteLine("Failure");
return;
}
}