Iterative solution for nCr problems?
The question here is whether or not there's a good iterative programmatic solution for computing all combinations of a group of values such that:
binomial(n, r[n]) + binomial(n, r[n-1]) + ... + binomial(n, r[n])+binomial(n, r[1])
Or in other words iterating over all 2^n-1 solutions for an nCr problem where r := {n,1}
ie/
So far the best I can come up with is something like:
{
System.Collections.ArrayList stack = new ArrayList(n);
int len = n.Length;
int grab = 2;
for(int c1 = 0; c1 < len; c1++)
{
int iters = System.Math.Pow(2, len-c2-1); //2^(n-1)
stack.Add(n[c1]);
//Send(stack) to some delegate
for(int c2 = 1; c2 < iters; c2++)
{
//Trying to figure out how to do this inner loop.
stack.RemoveRange(stack.Length-grab,grab-1);
}
}
}
ABCD
1 -
2 --
3 - -
4 - -
5 ---
6 -- -
7 - --
8 ----
Remove A
BCD
1 -
2 --
3 - -
4 ---
Remove B
CD
1 -
2 --
Remove C
D
1 -
Remove D, Done.
Notice that it follows Pascal triangle:
1, 3, 3, 1
1, 2, 1
1, 1
1
For ABCD if I want to find a pattern of one I remove the first "A". Other patterns of one include B, C, and D, we handle them in their own loops.
If I want to find patterns of two in ABCD that use `A` I get AB, AC, AD. To find a pattern of three using `A` there's ABC, ABD, ACD. Finally there's only one pattern of four - ABCD.
The formula we're seeing in action is:
4C1 - 3C1 = 1
4C2 - 3C2 = 3
4C3 - 3C3 = 3
4C4 - 3C4 = 1
This works for any row in Pascals Triangle.
5C1 - 4C1 = 1
5C2 - 4C2 = 4
5C3 - 4C3 = 6
5C4 - 4C4 = 4
5C5 - 4C5 = 1
The general form is:
Note if we could find a better way to do this by just iterating over the entire row, without having to figure out the number of iterations per number of combinations per element we'd just need to compute:
2^(n-1)
ie/
1 = 2^(1-1) = 1
1+1 = 2^(2-1) = 2
1+2+1 = 2^(3-1) = 4
1+3+3+1 = 2^(4-1) = 8
1+4+6+4+1 = 2^(5-1) = 16
