Associated Topics || Dr. Math Home || Search Dr. Math

### Finding All Combinations of Numbers

```Date: 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!

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;
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)
{
data.begin()+size,

// 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
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/
```
Associated Topics:
High School Calculators, Computers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search