Integer Permutations I Think!

[apophas]

I am not the greatest with math. And I cannot even think of where to start with this problem.

I have 36 numbers in sets of 5. (eg. 1-2-3-4-5, 2-3-4-5-6 etc..)
I need to find all the possible combinations of these numbers which total the same sum.

For instance the lowest sum would be:

1 + 2 + 3 + 4 + 5 = 15

The highest possible sum is

32 + 33 + 34 + 35 + 36 = 170.

Now every five number combination within these 36 numbers will sum up between 15 and 170.

How would I go about this in vb.net to produce all the possible combinations which would total say 92.

Thanks in advance

[jemidiah]

You can't reuse numbers? That is, 1+1+1+1+1 doesn't count. Let's impose an artificial constraint on our sequences--that they be ascending. This will prevent us from double counting. You say you have 36 sets of 5--when you make a "five number combination within these 36 numbers", you mean you choose one item from each of 5 of your sets? Or you choose 5 of the numbers from 1 to 36?

Assuming you have an array of numbers [1, 2, ..., 36] and you want to find all combinations of these numbers that add up to 92, you could do the following:

For a=1 to 36
    For b=a+1 to 36
        For c = b+1 to 36
            For d = c+1 to 36
                For e = d+1 to 36
                    If a+b+c+d+e = 92 Then MsgBox "found one."
                Next
            Next
        Next
    Next
Next

This could be optimized somewhat. You could test to see if your partial sums have gotten too large and break out of the loop early. After you pick a, b, c, and d, you've also uniquely determined e, which would save you one loop. The question is, how large are the partitions you want to find?

Also, this type of problem is called an integer partition.

[apophas]

Well I figured it out with the help of Shaggy from a previous post.
I'm using a form with a Button and a Richtextbox call Rtb0.
First I fill a list of strings with all possible 5 number combinations.
Then I devide each combination into a temporary array. Then I
added the value of each number in each combination to get my total.
Then I printed the totals to a richtextbox. Take a look, I'm sure it can
use some fine tuning.

Private Combinations As New List(Of String)

    Public Sub SetUpStrings_All(ByVal initString As String, ByVal sInt As Integer, ByVal lev As Integer)
        Dim st2 As String
        Dim count As Integer = Triples.Count

        For x As Integer = sInt To 36
            If x < 10 Then
                st2 = "0" & x.ToString
            Else
                st2 = x.ToString
            End If

            If lev = 0 Then
                Combinations.Add(initString & "-" & st2)
            ElseIf initString = "" Then
                SetUpStrings_Triples(st2, x + 1, lev - 1)
            Else
                SetUpStrings_Triples(initString & "-" & st2, x + 1, lev - 1)
            End If
            
        Next
    End Sub
Private Sub Button1_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles Button5.Click
        Dim temp() As String = Nothing
        Dim count As Integer = Nothing
        Dim Startnum As Integer = Nothing
        Dim Endnum As Integer = Nothing
        Dim Largest(155) As Integer
        Dim TempInt As Integer = Nothing

        SetUpStrings_All("", 1, 4)
        
        For i = 0 To Combinations.Count - 1
            temp = Combinations(i).Split("-"c)
            For j = 0 To 4
                count += Val(temp(j))
            Next

            Totals.Add(count)

            count = Nothing
            
        Next
        count = Nothing
        Totals.Sort()
        Rtb0.Clear()
        For k = 15 To 170
            Startnum = Totals.IndexOf(k)
            Endnum = Totals.LastIndexOf(k)
            TempInt = Endnum - Startnum
            If TempInt = 0 Then TempInt = 1
            
            Rtb0.Text += Environment.NewLine & k.ToString & " -->" & TempInt.ToString
            Largest(count) = Endnum - Startnum
            count += 1
        Next

        

    End Sub