all combinations from a set of numbers
-
I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so... Problem: I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more) the user will give in 3 number for example: 1 , 5 , 19 then the programme needs to give the following combinations: 1, 5, 19 1, 19, 5 5, 1, 19 5, 19, 1 19, 1, 5 19, 5, 1 I've been searching for some algoritme our other way to do this for several weeks now and just can't find it any ideas on how I could achieve this??
If my help was helpfull let me know, if not let me know why. The only way we learn is by making mistaks.
Hi, if you want to list all combinations, recursion is what you need. Build a method that takes a collection as an input, and let a for loop pick one element, remove it, then call recursively with wath remains in the collection, until the collection is empty; then return. BTW: if your collection is ordered, and your method picks in that same order, the result will be ordered too. Warning: for n elements, the recursion depth will be n, the number of combinations n! :)
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips: - make Visual display line numbers: Tools/Options/TextEditor/... - show exceptions with ToString() to see all information - before you ask a question here, search CodeProject, then Google
-
I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so... Problem: I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more) the user will give in 3 number for example: 1 , 5 , 19 then the programme needs to give the following combinations: 1, 5, 19 1, 19, 5 5, 1, 19 5, 19, 1 19, 1, 5 19, 5, 1 I've been searching for some algoritme our other way to do this for several weeks now and just can't find it any ideas on how I could achieve this??
If my help was helpfull let me know, if not let me know why. The only way we learn is by making mistaks.
char[] harfler = new char[7]; harfler[0] = tb1.Text.ToCharArray()[0]; harfler[1] = tb2.Text.ToCharArray()[0]; harfler[2] = tb3.Text.ToCharArray()[0]; harfler[3] = tb4.Text.ToCharArray()[0]; harfler[4] = tb5.Text.ToCharArray()[0]; harfler[5] = tb6.Text.ToCharArray()[0]; harfler[6] = tb7.Text.ToCharArray()[0]; List liste = new List(); for (int i = 0; i < harfler.Length; i++) { for (int j = (i + 1) % 7, x = 0; x < harfler.Length; x++) { if (i != j) { for (int k = (j + 1) % 7, y = 0; y < harfler.Length; y++) { if (k != i && k != j) { liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k]); for (int l = (k + 1) % 7, z = 0; z < harfler.Length; z++) { if (l != i && l != j && l != k) { liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l]); for (int m = (l + 1) % 7, t = 0; t < harfler.Length; t++) { if (m != i && m != j && m != k && m != l) { liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m]); for (int n = (m + 1) % 7, v = 0; v < harfler.Length; v++) { if (n != i && n != j && n != k && n != l && n != m) { liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m] + "" + harfler[n]); for (int o = (n + 1) % 7, q = 0; q < harfler.Length; q++) { -
Hi, if you want to list all combinations, recursion is what you need. Build a method that takes a collection as an input, and let a for loop pick one element, remove it, then call recursively with wath remains in the collection, until the collection is empty; then return. BTW: if your collection is ordered, and your method picks in that same order, the result will be ordered too. Warning: for n elements, the recursion depth will be n, the number of combinations n! :)
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips: - make Visual display line numbers: Tools/Options/TextEditor/... - show exceptions with ToString() to see all information - before you ask a question here, search CodeProject, then Google
Recursion is a bad thing. You can almost always remove recursion from an algorithm using a simple stack. Case in point, you can remove recursion from the suggested algorithm with a stack. Something like this: 1 on Stack 5 on Stack 19 on Stack Start popping -> 1,5,19 19 on Stack 5 on Stack Start popping -> 1,19,5 etc ... HossFly
-
Recursion is a bad thing. You can almost always remove recursion from an algorithm using a simple stack. Case in point, you can remove recursion from the suggested algorithm with a stack. Something like this: 1 on Stack 5 on Stack 19 on Stack Start popping -> 1,5,19 19 on Stack 5 on Stack Start popping -> 1,19,5 etc ... HossFly
Hoss Fly wrote:
Recursion is a bad thing
Nonsense! Recursion is simply one tool that any professional should consider. There may be performance issues in some applications, but often you can't beat it for simplicity and elegance. Recursive descent parsing is an excellent example.
Hoss Fly wrote:
You can almost always remove recursion from an algorithm using a simple stack
So why not use the processor stack - i.e. recursion. If you use built-in support rather than roll your own stack the code may be cleaner and less error prone. Unless the number of elements is large (in which case there is no point enumerating all n! permutations), recursion is a perfectly valid method of solution to consider.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
Hoss Fly wrote:
Recursion is a bad thing
Nonsense! Recursion is simply one tool that any professional should consider. There may be performance issues in some applications, but often you can't beat it for simplicity and elegance. Recursive descent parsing is an excellent example.
Hoss Fly wrote:
You can almost always remove recursion from an algorithm using a simple stack
So why not use the processor stack - i.e. recursion. If you use built-in support rather than roll your own stack the code may be cleaner and less error prone. Unless the number of elements is large (in which case there is no point enumerating all n! permutations), recursion is a perfectly valid method of solution to consider.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
You made my point for me. You shouldn't use recursion if you do not know the recursion depth. Whereas with a stack it is never an issue. I can describe many a problem where one cannot KNOW the recursion depth in advance (Flood Fill, Point Insertion w/r to Triangulation, clipping, etc...) I have fixed recurssion based algorithms in two commercial products. The crashes this type of logic causes is often very difficult to catch. Try finding it in millions of lines of code and you will have the same opinion. It is probably ok for some text book or academic problems. problem is developers fail to realize the stack problem and take the easy approach. I advocate thinking stack first, and recursion second (or last resort, or never.) HossFly
-
I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so... Problem: I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more) the user will give in 3 number for example: 1 , 5 , 19 then the programme needs to give the following combinations: 1, 5, 19 1, 19, 5 5, 1, 19 5, 19, 1 19, 1, 5 19, 5, 1 I've been searching for some algoritme our other way to do this for several weeks now and just can't find it any ideas on how I could achieve this??
If my help was helpfull let me know, if not let me know why. The only way we learn is by making mistaks.
Hmmm... that looks like permutations to me, not combinations. :)
-
You made my point for me. You shouldn't use recursion if you do not know the recursion depth. Whereas with a stack it is never an issue. I can describe many a problem where one cannot KNOW the recursion depth in advance (Flood Fill, Point Insertion w/r to Triangulation, clipping, etc...) I have fixed recurssion based algorithms in two commercial products. The crashes this type of logic causes is often very difficult to catch. Try finding it in millions of lines of code and you will have the same opinion. It is probably ok for some text book or academic problems. problem is developers fail to realize the stack problem and take the easy approach. I advocate thinking stack first, and recursion second (or last resort, or never.) HossFly
I agree.
Steve
-
I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so... Problem: I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more) the user will give in 3 number for example: 1 , 5 , 19 then the programme needs to give the following combinations: 1, 5, 19 1, 19, 5 5, 1, 19 5, 19, 1 19, 1, 5 19, 5, 1 I've been searching for some algoritme our other way to do this for several weeks now and just can't find it any ideas on how I could achieve this??
If my help was helpfull let me know, if not let me know why. The only way we learn is by making mistaks.
In C++ something like this is the way to go: -------------------------------------------- // Console.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include #include void main() { using namespace std; int Numbers[] = {1, 5, 19}; int *pOnePastEnd = Numbers + sizeof(Numbers)/sizeof(Numbers[0]); sort(Numbers, pOnePastEnd); copy(Numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; while (next_permutation(Numbers, pOnePastEnd)) { copy(Numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; } } Steve
-
You made my point for me. You shouldn't use recursion if you do not know the recursion depth. Whereas with a stack it is never an issue. I can describe many a problem where one cannot KNOW the recursion depth in advance (Flood Fill, Point Insertion w/r to Triangulation, clipping, etc...) I have fixed recurssion based algorithms in two commercial products. The crashes this type of logic causes is often very difficult to catch. Try finding it in millions of lines of code and you will have the same opinion. It is probably ok for some text book or academic problems. problem is developers fail to realize the stack problem and take the easy approach. I advocate thinking stack first, and recursion second (or last resort, or never.) HossFly
As Peter already told you, recursion has its merits; it is often abused, but in this case it is the right approach. My last remark (the depth n and result count n!) was intended to illustrate that: if you care to consume n! results, then a stack depth of n would not be an obstacle. :)
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips: - make Visual display line numbers: Tools/Options/TextEditor/... - show exceptions with ToString() to see all information - before you ask a question here, search CodeProject, then Google
-
In C++ something like this is the way to go: -------------------------------------------- // Console.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include #include void main() { using namespace std; int Numbers[] = {1, 5, 19}; int *pOnePastEnd = Numbers + sizeof(Numbers)/sizeof(Numbers[0]); sort(Numbers, pOnePastEnd); copy(Numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; while (next_permutation(Numbers, pOnePastEnd)) { copy(Numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; } } Steve
I see I got 2ed. Well it works perfectly and the OP didn't mention a language. If he's got a C++ compiler he can look in the source code and adapt the algorithm used to another language. Alternatively he could download STLport and do the same.
Steve
-
I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so... Problem: I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more) the user will give in 3 number for example: 1 , 5 , 19 then the programme needs to give the following combinations: 1, 5, 19 1, 19, 5 5, 1, 19 5, 19, 1 19, 1, 5 19, 5, 1 I've been searching for some algoritme our other way to do this for several weeks now and just can't find it any ideas on how I could achieve this??
If my help was helpfull let me know, if not let me know why. The only way we learn is by making mistaks.
This is pseudocode for your solution: ListCombinatoricalOrder(List L) if (L is empty) return int n = L.Count if (n == 1) Write L[0] return Write(L) ListCombinatoricalOrder(empty, L, n) Done ListCombinatoricalOrder(List Prefix, List comb, int count) for (int i = 0; i < count; ++i) List newPre = Prefix append comb[i] List newComb = comb subtract comb[i] if (i != 0) Write(newPre, newComb) ListCombinatoricalOrder(newPre, newComb, count - 1) Done WHERE: Write(L) will write the entire list Write(newPre, NewComb) will Write the list newPre then append the list NewComb to it Notice the is an output generating algorithm not suited well for a library. But I left the details to you to make it more generic. This is just an idea of how to go about solving the combinatorical problem. I hope this helps. --Avi -- modified at 4:42 Sunday 14th October, 2007