473,836 Members | 1,379 Online

# 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

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 5413
This sort of thing can be found in Google (e.g. "generate combinations
algorithm"). For example,
"Ryan" <po****@mchsi.c om> wrote in message
news:D27Ab.4319 87\$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

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.c om> wrote in message
news:D27Ab.4319 87\$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

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.WriteLi ne("");
}
}

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" <davidbaxterbro wne no potted me**@hotmail.co m> wrote in
message news:eW******** ******@TK2MSFTN GP09.phx.gbl...

"Ryan" <po****@mchsi.c om> wrote in message
news:D27Ab.4319 87\$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

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.WriteLi ne("");
}
}

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 9491 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 2966 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^n - NULL): 1, 2, 3 1, 2 2, 3 2 6038 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 like to offer advice on how to approach this problem, it would be much appreciated. Thanks, d 4 5544 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 numbers between the bounds. e.g if lower_bound = 5, upper bound = 7, size = 3, the algorithm would generate: 8 10959 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 detailed example of what I want: Given a vector containing an arbitrary number of vectors, each of which contains an arbitrary number of elements, generate a new vector in which each element consists of one element taken from its corresponding... 19 7559 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 2424 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 7429 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 assume the best way to do this would be either using closures or creating some sort of iterator class. Any guidance on how to get started? Thanks, 2 2276 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 combinations should be of a size that is a multiple of 3. 0 9825 by: marktang | last post by: ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of... 0 9672 by: Hystou | last post by: Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,... 0 10854 by: Oralloy | last post by: Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in... 1 10601 by: Hystou | last post by: Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,... 0 9388 by: agi2029 | last post by: Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea... 1 7794 by: isladogs | last post by: The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will... 0 6981 by: conductexam | last post by: I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();... 0 5652 by: TSSRALBI | last post by: Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls... 2 4023 by: muto222 | last post by: How can i add a mobile payment intergratation into php mysql website.