Finding All Combinations of NumbersDate: 07/23/2002 at 16:25:55 From: Michael Slaney Subject: Algorithm to find all possible combinations of numbers Hi, I'm looking for an algorithm to find all possible combinations of numbers using a pre-defined set. For example: Set = {10, 1, 2, 7, 6, 1, 5} (n=7 elements) Looking for number (x = 8) Should return the following solutions based on the set defined above: {7, 1} {6, 2} {6, 1, 1} {5, 2, 1} If you have some ideas, or can point me in the right direction, I would greatly appreciate it! Thanks for your help, Michael Slaney Date: 07/26/2002 at 00:02:53 From: Doctor Jeremiah Subject: Re: Algorithm to find all possible combinations of numbers Hi Michael, This is what I would try: For each number of addends you want (from 2 up to N), generate every possible permutation of the sequence. For each permutation add up the number of addends and if it sums to the total then print it; otherwise ignore it. But you also must make sure that you aren't repeating previous permutations and that you only use one of each identical combination. Here is how I wrote it: #include <iterator> #include <vector> #include <iostream> // we need a functor that will sum a range or iterators class adder : public unary_function<int, void> { public: int sum; adder() : sum(0) {} void operator()(int x) {sum+=x;} }; // we need a functor that will determine if a range of // iterators is sorted in descending order class sortcheck : public unary_function<int, void> { public: int sorted; int last; sortcheck() : sorted(true),last(0x7FFFFFFF) {} void operator()(int x) { if(x<=last) { last=x; } else { sorted=false; } } }; // this program will read the values from standard input but // expects the requested sum to come from the command line int main(int argc,char *argv[]) { int count=0; int sum = atoi(argv[1]); // first command line parameter int size; vector<int> data; // holds the data vector<int> last; // holds a copy so we can check duplication // fill the vector with data from standard input copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(data)); // now do the whole thing starting with 2 numbers and going up for(size=2;size<data.size();size++) { // clear the backup and fill it with zeros last.clear(); fill_n(back_inserter(last),data.size(),0); // always sort before starting a permutation loop // so that you get all the permutations sort(data.begin(),data.end()); while(next_permutation(data.begin(),data.end())) { // now we have the next permutation // but if the first X digits are the same as // last time then its the same one for us if(!equal(data.begin(),data.begin()+size,last.begin())) { sortcheck result=for_each(data.begin(), data.begin()+size, sortcheck()); // we must be sure that we only return the // same combination once, so choose the one // in descending order if(result.sorted) { adder result=for_each(data.begin(), data.begin()+size, adder()); // if it adds up then print it if(result.sum==sum) { cout<<"( "; copy(data.begin(), data.begin()+size, ostream_iterator<int>(cout," ")); cout<<")"; cout<<endl; count++; } } } // before doing the next permutation, save // the current one for the 'equals' check copy(data.begin(),data.end(),last.begin()); } } return count; } - Doctor Jeremiah, The Math Forum http://mathforum.org/dr.math/ Date: 07/26/2002 at 15:55:55 From: Michael Slaney Subject: Algorithm to find all possible combinations of numbers Hi Doctor Jeremiah, First let me thank you so much for the work you put into this...I was expecting a short paragraph about how to do it...your efforts are greatly appreciated! I'm pretty good with Visual Basic but haven't any experience with C++ (which is what I think the language is you used). I have a copy of Visual C++ .Net and Visual C# .Net; would either of those work to compile and test this program? I'd like to compile this program and step through the code to see what it's doing. Should make things clearer so I can then translate it into VB. Again, thanks so much for taking the time to come up with a solution for me. Hope to hear back from you soon! Kind regards, Michael Slaney Date: 07/26/2002 at 20:09:10 From: Doctor Jeremiah Subject: Re: Algorithm to find all possible combinations of numbers Hi Michael Visual C++ .NET should compile it. It should be easy to translate it to VB except for one thing - I used the next_permutation function from the C++ library to get it to find the different combinations. VB doesn't have an equivalent function, so you will have to write something equivalent. So here is how I would do it in VB: Option Explicit Sub Display(Values() As Integer, size As Integer) Dim i As Integer For i = 1 To size Debug.Print Values(i); Next Debug.Print End Sub Sub Fill(Values() As Integer, size As Integer, Data As Integer) Dim i As Integer For i = 1 To size Values(i) = Data Next End Sub Sub Sort(Values() As Integer, size As Integer) Dim i As Integer Dim j As Integer For i = 1 To size For j = 1 To size - i If Values(j + 1) < Values(j) Then Call Swap(Values, j, j + 1) End If Next Next End Sub Function Total(Values() As Integer, size As Integer) As Long Dim i As Integer Dim Sum As Long Sum = 0 For i = 1 To size Sum = Sum + Values(i) Next Total = Sum End Function Sub Copy(First() As Integer, Second() As Integer, size As Integer) Dim i As Integer For i = 1 To size First(i) = Second(i) Next End Sub Function Equal(First() As Integer, Second() As Integer, size As Integer) As Boolean Dim i As Integer Dim result As Boolean result = True For i = 1 To size If Not First(i) = Second(i) Then result = False Exit Function End If Next Equal = result End Function Function Sorted_Descending(Values() As Integer, size As Integer) As Boolean Dim i As Integer Dim Last As Long Dim result As Boolean Last = 2147483647# ' biggest possible positive number result = True For i = 1 To size If Values(i) <= Last Then Last = Values(i) Else result = False End If Next Sorted_Descending = result End Function Sub Swap(Values() As Integer, i As Integer, j As Integer) Dim temp As Integer temp = Values(i) Values(i) = Values(j) Values(j) = temp End Sub Sub Reverse(Values() As Integer, First As Integer, Last As Integer) Dim i As Integer Dim j As Integer i = First j = Last While i <= j Call Swap(Values, i, j) i = i + 1 j = j - 1 Wend End Sub Function next_permutation(Values() As Integer, size As Integer) As Boolean Dim i As Integer Dim j As Integer Dim k As Integer If size = 1 Then next_permutation = False Exit Function End If i = size While True k = i i = i - 1 If Values(i) < Values(k) Then j = size While Not Values(i) < Values(j) j = j - 1 Wend Call Swap(Values, i, j) Call Reverse(Values, k, size) next_permutation = True Exit Function End If If i = 1 Then Call Reverse(Values, 1, size) next_permutation = False Exit Function End If Wend End Function Private Sub Combinations(Values() As Integer, length As Integer, Sum As Integer) Dim Last(10) As Integer Dim size As Integer For size = 2 To length Call Fill(Last, size, 0) Call Sort(Values, length) ' have to do entire array While next_permutation(Values, length) ' have to do entire array If Not Equal(Last, Values, size) Then If Sorted_Descending(Values, size) Then If Total(Values, size) = Sum Then Call Display(Values, size) End If End If End If Call Copy(Last, Values, size) Wend Next End Sub Private Sub Test() Dim Values(10) As Integer Dim length As Integer Dim Sum As Integer Dim i As Integer length = 7 Values(1) = 10 Values(2) = 1 Values(3) = 2 Values(4) = 7 Values(5) = 6 Values(6) = 1 Values(7) = 5 Sum = 8 Call Display(Values, length) Call Combinations(Values, length, Sum) End Sub - Doctor Jeremiah, The Math Forum http://mathforum.org/dr.math/ Date: 08/10/2002 at 19:40:40 From: Michael Slaney Subject: Thank you Hi Doctor Jeremiah, Your algorithm worked perfectly - thanks so much! A routine to do this sounded simple, but after spending a lot of time on it I couldn't come up with anything. I really appreciate all the time you spent on this, as well as your quick response! Kindest regards, Michael Slaney Date: 08/11/2002 at 01:08:57 From: Doctor Jeremiah Subject: Re: Thank you Hi Michael, That wasn't a trivial piece of code. It seemed simple when I wrote it, but looking at it now all I can think is that it is much more complicated than you would expect. Unfortunately I still don't see a simpler solution. I am glad it worked for you! - Doctor Jeremiah, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/