473,323 Members | 1,537 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,323 software developers and data experts.

Combinations Algorithm

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
3 5355
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

"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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

36
by: rbt | last post by:
Say I have a list that has 3 letters in it: I want to print all the possible 4 digit combinations of those 3 letters: 4^3 = 64 aaaa
2
by: Peter R | last post by:
Hi, Probably this question was asked before, but what is the algorithm to generate all combinations based on N numbers? For example, for 3 elements = {1,2,3}, I'd like to generate a list of...
2
by: deancoo | last post by:
I've seen an algorithm for permutations, but I need to find combinations. Is there an STL equivalent to next_permutation for combinations? The material I'm finding is kinda light, if anyone would...
4
by: pauljwilliams | last post by:
Hi there, I'm looking for an algorithm that will generate combinations in the following way: Given a lower bound, and an upper bound, generate a set of size n containing all combinates of...
8
by: cayblood | last post by:
Hello, I have been interested in something kind of like the next_permutation from the STL algorithm library, except that I want it to find possible combinations of vector elements. Here is a more...
19
by: Thomas Cameron | last post by:
Hello all, I have an array of values which I would like to generate all possible combinations for. And example would be the values "a,b,c". This would produce the following: a ab abc ac
15
by: Thomas Cameron | last post by:
Hello all, I have an array of values which I would like to generate all possible combinations for. And example would be the values "a,b,c". This would produce the following: a ab abc ac b
7
by: Jacob JKW | last post by:
I need to iterate over combinations of n array elements taken r at a time. Because the value of r may vary quite a bit between program invocations, I'd like to avoid simply hardcoding r loops. I...
2
by: zgfareed | last post by:
Can anyone suggest an algorithm or function to generate combinations/ permutations of a group of substrings stored in a vector. The substrings consists of 3 letters and the resulting string...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.