432,650 Members | 1,823 Online + 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
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" 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" 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" wrote in message news:eW**************@TK2MSFTNGP09.phx.gbl... "Ryan" 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. 