printing all the combinations....Algorithm help....

[fenris]

I have been wrestling with this problem for a while and i can't seem to find any information on the internet about it.

The problem is this:
I have ten numbers (not necessarily sequential) and I want to print out all the 6 group combinations, ie 10 choose 6. I know the formula n_c_p = n!/(p!(n-p)!) which tells me how many combinations there are. I am stumped. It should also be able to handle arbritary n and p values ie, I should be able to input 25 numbers and have it generate all the 5 number combinations.

Any help would be appreciated. Pointers to websites would be appreciated as well

A simple example would be: 1,2,3,4,5 choose 3
123
124
125
134
135
145
234
235
245
345



Troy Williams B.Eng.
fenris@hotmail.com

 

[MichaelRed]

Troy,

This question is much more challenging than it looks. There are only a few technical issues, and one other issue.

This is limiting the results set.

n_c_p = n!/(p!(n-p)!)

Will grow (unmanageably) LARGE for 'innocently' small values of n & p. This - in turn - makes the problem -unmanageably large for processing/printing.

Look even at the problem you state as the sample. You need to calculate the factorial of 25. This will exceed the capability of a "Long", so you already need to go to a "Double". You will not achieve the precision necessary to even accuratly calculate the number of items you want to print out.

Even setting the types of the variables to "DOOUBLE", which does permit the calculation of the Example, the results are 3268760 (yes, that is 3.2 MILLION results). Either you have a LONG time to print this out - or you will attempt to store it (in whose Memory?) - or you will save it to disc. The latter being the least unreasonable from the computational perspective. BUT then how will you really use it?



MichaelRed
mred@duvallgroup.com
There is never time to do it right but there is always time to do it over

 

[fenris]

Michael,
I am not sure I quite follow your post?


Besides, I finally figured out how to accomplish what I wanted to do. And it works....

Here is the code:
=======================
Public Sub Combinations(numbers() As Long, p As Long, NumComboLabel As Label, Combinations As ListView)
'It outputs the number of different combinations to a listview control that was passed
'to it as well as putting out the number of combinations to the label that was passed to it
'The number of combinations is calculated
'according to the formula n_choose_p = n!/p!(n-p)!
Dim n As Long
Dim temp As Integer
n = UBound(numbers)
temp = LBound(numbers)

n = n - temp + 1 'the number of elements in the array
'================================
'make sure there is no illegal input
If p > n Or n < 1 Or p < 1 Then
MsgBox &quot;Illegal input in the Combinations function!&quot;, vbExclamation, &quot;Error&quot;
Exit Sub
End If
'================================
Dim NumCombo As Long
NumCombo = numCombinations(n, p) 'the number of possible combinations
NumComboLabel.Caption = &quot;The Number of Combinations are: &quot; & NumCombo

'Dim combo() As Long
'ReDim combo(temp To p)
'=========================
'indices
Dim i As Integer
Dim x As Integer
Dim y As Integer
Dim indices() As Integer
ReDim indices(p)
'=======================


CreateHeader Combinations, p

'========================

'initialize the indices

For i = 1 To p
indices(i) = i
Next i
Dim temp1() As Long 'used to hold the values
ReDim temp1(1 To p)

Dim upperLimits() As Long
ReDim upperLimits(1 To p)

'set the upperlimits for each of the indices
'for example, indices(p) = n

For i = 1 To p
upperLimits(i) = n - p + i
Next i

Dim z As Long



x = p

For z = 1 To NumCombo
'===================

'create array containing the numbers based on the indices
For i = 1 To p
temp1(i) = numbers(indices(i))
Next i
'===================
'Print out the combination
addNumbersToView Combinations, temp1
'=======================
x = p
Do While x >= 1
If x = p And indices(x) <> upperLimits(x) Then
indices(x) = indices(x) + 1
Exit Do
End If

If x < p And indices(x) <> upperLimits(x) Then
indices(x) = indices(x) + 1
For y = x + 1 To p
indices = indices(x) + (y - x)
Next y
Exit Do
End If

x = x - 1
Loop

'=====================
'
Next z
'Wend 'outer loop to loop through each of the different combinations
'========================
End Sub
'=======================
Public Function numCombinations(n As Long, p As Long) As Long
Dim temp As Long
'make sure that n is greater then p
If n < p Then
MsgBox &quot;n is smaller the p in numCombinations&quot;, vbExclamation, &quot;Error&quot;
Exit Function
End If
temp = factorial(CLng) / (factorial(CLng(p)) * factorial(CLng(n - p)))
numCombinations = temp

End Function
'=================================
Public Function factorial(n As Long) As Long
Dim i As Long
Dim temp As Long
temp = 1
For i = 1 To n
temp = temp * i

Next i
factorial = temp

End Function
'=====================================
'create headers in a listview
Public Sub CreateHeader(lstView As ListView, p As Long)
Dim hdrNumber() As String
Dim i As Long
ReDim hdrNumber(1 To p)

For i = 1 To p
hdrNumber(i) = CStr(i)
Next i

'add the columns
For i = 1 To p
lstView.ColumnHeaders.Add , , hdrNumber(i), 500
Next i

End Sub
'====================================
Public Sub addNumbersToView(lsvView As ListView, numbers() As Long)
Dim itmx As ListItem
Dim i As Long
Dim upper As Long
Dim lower As Long
upper = UBound(numbers)
lower = 1

Set itmx = lsvView.ListItems.Add(, , numbers(lower))

'set the subitems
For i = lower To upper - 1
itmx.SubItems(i) = CStr(numbers(i + 1))
Next i


End Sub
'====================================

Basically, all you have to do is put a listview control on a form along with a label, and when the form loads, pass an array of integers with a p value and the name of the listview control and the label, it will print out the combinations of numbers. I am sure with modifications it would do a better job. Besides if I see that the numbers I want to use get too large, then I will enter some error checking.



Troy Williams B.Eng.
fenris@hotmail.com

 

[TRYP]

can the same number be used in the combination more than once ?

ex.
inputs- 1,2,3,4,5,6,7,8,9,10
combo- 2,2,2,3,3,3
?????


-tryp

 

[Durkin]

I know you've got it working for yourself but I liked the idea of the problem so here is my solution. It outputs the results to a file rather than a list view and instead of calculating the results it just counts them as they are calculated. Basically, you just pass in the array and the length of the combinations. Most of my variables are ints so the size of the numbers are limited but the logic is right.
The idea behind it is that the actual values are irrelevant - they could be strings or anything else. So, if there are twenty-five elements in the array just consider them numbers 0 to 24 and things start to get simpler. Every number should be smaller than the one to the right of it. That way the first and the last elements will be
0,1,2,3,4
& 19,20,21,22,23,24
and all combinations in between.
My routine fills itself in recursively, so I think at a certain level there would be to many calls on the stack and it would crash.
Anyway, here it is. The first routine starts up the loop and the second does the calcs.

Public Sub SetUpLoop(intArray() As Integer, CombinationLength As Integer)
Dim CombArray() As Integer
Dim Ffile As Integer
Dim i As Integer
Dim Total As Double

Ffile = FreeFile
Open &quot;C:\Combinations.txt&quot; For Output As #Ffile
ReDim CombArray(0)

For i = 0 To UBound(intArray)
CombArray(0) = i
GetDistinctCombinations intArray, CombArray, CombinationLength - 1, Ffile, Total
Next i
Print #Ffile, &quot;Total No. &quot; & Total
Close #Ffile

End Sub

------------------------------------------------------------

Public Sub GetDistinctCombinations(FullArray() As Integer, UsedArray() As Integer, NoOfSpaces As Integer, Ffile As Integer, TotalNum As Double)
Dim TopNum As Integer
Dim NewUsedArray() As Integer
Dim strComb As String
Dim i As Integer

ReDim NewUsedArray(UBound(UsedArray))

For i = 0 To UBound(UsedArray)
strComb = strComb & FullArray(UsedArray(i)) & &quot;,&quot;
NewUsedArray(i) = UsedArray(i)
Next i

TopNum = UsedArray(UBound(UsedArray))
If NoOfSpaces = 1 Then
For i = TopNum + 1 To UBound(FullArray)
Print #Ffile, strComb & FullArray(i)
TotalNum = TotalNum + 1
Next i
Else
ReDim Preserve NewUsedArray(UBound(UsedArray) + 1)
For i = TopNum + 1 To UBound(FullArray)
NewUsedArray(UBound(NewUsedArray)) = i
GetDistinctCombinations FullArray, NewUsedArray, NoOfSpaces - 1, Ffile, TotalNum
Next i
End If
End Sub
Durkin
alandurkin@bigpond.com

 

[MichaelRed]

Alan,

Interesting. I wrote a small wrapper to generate the intarray and pass it and the number of combos to your start program:

Public Function basTestCombinations(Nums As Integer, Perms As Integer)

    Dim intArray() As Integer
    Dim Idx As Integer
    
    ReDim intArray(Nums)
    For Idx = 0 To Nums
        intArray(Idx) = Idx
    Next Idx
        
    Call SetUpLoop(intArray(), Perms)

End Function

Calling this:
? basTestCombinations(25, 10)
(from debug)

You will not run out of stack space (within this lifetime) as the recursion is really only in the second routine, which is probably just the 'Perms' argument in my wrapper. I was checking the 'Call Stack' through the process and never actually found more than 8 copies of the recursive routine there at the same time.

Other problems do arise:

I let this &quot;run&quot; for ~ 1/2 hour. It was up to ~4.2 Meg combinations (I think this is wrong, as the formula predicts there should be ~3.2 Million), however it tends to 'prove' that the stack issue is not a real factor.

When I stopped the process, I looked at the 'SetUpLoop' status, and found 'i' in the loop was only up to 8, so I was apparently only ~ 1/3 of the way through the process and had already exceeded the expected number of combinations by 25 to 30%.

The file created by the process - to the point of interruption was ~1.22 MBytes (this is reasonably consistient w/ the 4.2 Million reords noted above). I have a modest system (250 MHz, 128 Meg Memory and 40 Gig HD), however with only a few programs loaded, it took ~15 Minutes to open the file, and longer than that to traverse it (I never actually got to the bottom, as other matters do (occassionally) require attention.

So, back to the beginning, I see the improvement in the process - you avoid the calculation of the factorials, however the results do not appear to be practically useable. As a (HUGE) text file, no human can reasonably be expected to make any real use of the content. If you 'translate' the output to a database format, you will be stressing all but the 'BIG BOYS' in ability to reasonably handle the record count. Your approach appears to be much more pratical in generating the combiniations - but no better in the overall sense.



MichaelRed
mred@duvallgroup.com
There is never time to do it right but there is always time to do it over

 

[MichaelRed]

Durkin,

mea culpa. I was computing the combinations ref base 1, but inputting the numbers base 0. It DOES make the difference in the number of combiniations.

YOU are correct.

Apologies for the err.

Michael.



MichaelRed
mred@duvallgroup.com
There is never time to do it right but there is always time to do it over

 

[fenris]

Thank you all for your responses....They are much appreciated.

Michael, I had a chance to reflect on what you were saying and it does make sense to me now.

TRYP,
The problem that I was working on required the combinations to have no repeating values, similar to a lottery type deal.

Durkin, I like your approach! I have never been very good at coming up with my own recursive functions. The algorithm that I loosely based my program on was written in java and it calculated the number of combinations, by simply incrementing a counter such as you have done.


Thanks for the responses.....

Troy Williams B.Eng.
fenris@hotmail.com