By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,650 Members | 1,823 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,650 IT Pros & Developers. It's quick & easy.

Combinations Algorithm

P: n/a
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 :/
Nov 15 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
This sort of thing can be found in Google (e.g. "generate combinations
algorithm"). For example,
http://remus.rutgers.edu/~rhoads/Code/code.html
"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 :/

Nov 15 '05 #2

P: n/a

"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;
}
Nov 15 '05 #3

P: n/a
Thanks for the tips and code David they were very helpful.

"David Browne" <davidbaxterbrowne no potted me**@hotmail.com> wrote in
message news:eW**************@TK2MSFTNGP09.phx.gbl...

"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;
}

Nov 15 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.