Ryan said:
I've been trying to find an algorithm that will output all of the possible
combinations of items in an array. I know how to find the number of
combinations for each set using
nCr=n!/(r!(n-r)!)
set being possible combinations of r objects from a group of n objects.
e.g. n=5 r=3 using A,B,C,D,E as items
ABC ABD ABE ACD ACE
ADE BCD BCE BDE CDE
I can't seem to come up with an algorithm to figure out what each set is.
Any help is much appreciated, I've been stuck on this for a while :/
Here's a C# function that will give you random access into the combinations.
The algorithm walks Pascal's Triangle from the node whose value is nCr to
the left-hand edge. At each step if the index of the choice is less than
number above and to the left, then we pick an element and move up and left.
Otherwise we reduce the index, and move above and to the right, and skip an
element. Eventually we end up on the left edge, having picked exactly r of
the n elements.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 T T 5 1
Eg for n=5 r=3:
1
1 1
1 2 1
3 3 1
6 4
T
Start at 5C4=10
1: 1<=6 so pick A and move up and left (to 6)
1<=3 so pick B and move up and left (to 3)
1<=1 so pick c and move up and left (to 1): ABC
6: 6<=6 so pick A and move up and left (to 6)
6>3 so subtract 3, skip B and move up and right (to 3)
3>2 so Subtract 2, skip C and move up and right (to 1)
1<=2 so Pick D and move up and left (to 1)
1<=2 so Pick E and move up and left (to 1): ADE
7: 7>6 so subtract 6, skip A and move up and right (to 4)
1<=3 so Pick B and move up and left (to 3)
1<=3 so Pick C and move up and left (to 2)
1<=2 so Pick D and move up and left (to 1): BCD
Anyway here it is:
static void Main(string[] args)
{
int n = 5;
int r = 3;
long combinations = nCr(n,r);
for (int i=1; i <= combinations;i++)
{
int[] choice = GetChoice(i,n,r);
for (int j = 0; j < r;j++)
{
Console.Write((Char)((int)'A'+choice[j]));
}
Console.WriteLine("");
}
}
static long nCr(int n, int r)
{
//calculate nCr like this to stay in bounds.
//notice you never have to store n!
//all intermediate results are < nCr*r
long rv = 1;
r = Math.Min(r,n-r);
for (long i = 0; i < r; i++)
{
rv = (rv * (n-i))/(i+1);
}
return rv;
}
static int[] GetChoice(long choiceNum, int n, int r)
{
//choiceNum is 1 through nCr
//returns an array of your choice
int[] rv = new int[r];
long ii = choiceNum;
int ix = 0;
int next = 0;
int rr = r;
int nn = n;
do
{
long nnCrr = nCr(--nn,--rr);
if (ii <= nnCrr)
{
rv[ix++]=next++;
}
else
{
rr++;
ii -= nnCrr;
next++;
}
} while (ix < r);
return rv;
}
