"Ryan" <po****@mchsi.com> wrote in message

news:D27Ab.431987$HS4.3401929@attbi_s01...

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;

}