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!

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/