Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 375

# Help Creating Combination Algorithm (Not Permutation!)

Hi,

I have a problem which I hope someone can help me with. I need to create an algorithm which takes in two numbers (n for sample size, r for size of different combinations, representing the 'nCr' mathematical combination notation) and returns a list (array, collection, whatever is most memory-efficient) of all the combinations of numbers.

To help clarify, I imagine something like this (in pseudo-code):

Dim arrResults() As Variant 'Holds resulting combinations of numbers
Dim n As Integer, r As Integer

arrResults = Combine(n, r) 'assume array is returned

Private Function Combine(sampleSize As Integer, combinationSize As Integer) As Variant()

'Algorithm in here produces combinations of numbers and return results

End Function

For example, let n = 4 and r = 2:

arrResults = Combine(4, 2)

'arrResults is the following, notice that order does NOT matter (i.e. "1,2" = "2,1"). Therefore:

arrResults(0) = "1,2"
arrResults(1) = "1,3"
arrResults(2) = "1,4"
arrResults(3) = "2,3"
arrResults(4) = "2,4"
arrResults(5) = "3,4"

In the real version, I will be using a sample size of 40 and a combination size of 5, giving a total of 40 C 5 = 658008 elements, as opposed to the 6 above. As a result, I want to make sure whatever algorithm and data structure I use to store the data are memory efficient (e.g. array vs. dictionary vs. collection, etc).

Also, in the example I put each array element in as a string but that is arbitrary, though I need to be able to parse the different numbers in the array. In other words "1,2" has to be able to be parsed to 1 and 2, thus it can't be returned as "12" or 12. I was thinking of using strings because the Split function nicely separates the string into an array, which suits the function of what I need to use the results for.

Thanks in advance for help and I'll be happy to clarify any questions.

0
acsher3
• 4
• 3
1 Solution

Commented:
This sounds like a homework problem

I don't know if VB can build a data structure that can handle the size.  The only way may be to write the results as tabulated to a file.

Basic Algorithm - not really efficient

for i = 1 to 36
for j = i+1 to 37
for k = j+1 to 38
for l = k+1 to 39
for m = l+1 to 40
print i,j,k,l,m
next m
next l
next k
next j
next i

mlmcc

0

Author Commented:
Thanks mlmcc.

I wish it were a homework problem, then I wouldn't have to worry (as much) about being efficient. Instead it's small part of a datamining application I'm writing. Your idea works for getting the correct combinations, but creates around a 15 mb text file (I haven't yet tried putting it into a structure). Maybe someone can come up with a more efficient way of doing it.
0

Commented:
I haven't tried it, does it create duplicates?

mlmcc
0

Author Commented:
the function works well in that it doesn't produce duplicates. however, its hard-coded for the sample size of 40 and combination size of 5, which works well for now, but the ultimate goal is to have a function that I can pass two arguments to and create the results. also, i like the idea of saving the results to a file, but is there any way to make the file smaller (binary file for example?) When I change the combination size to 6, I create a text file that is over 65 mb in size. it's doable, but obviously i'd like to optimize as much as possible.

thanks.
0

Commented:
I really don't know a good way to handle changing the combinations 5 of 40.  The 40 is easy to change.  The 5 is harder
I assume you are working in VB

Create a form

Put 2 text boxes
txtMaxNbr
txtNbrSelections

Put a command button on it
Put the following code behind it

for i = 1 to txtMaxNbr-4
for j = i+1 to txtMaxNbr-3
for k = j+1 to txtMaxNbr-2
for l = k+1 to txtMaxNbr-1
for m = l+1 to txtMaxNbr
print i,j,k,l,m
next m
next l
next k
next j
next i

A poor man's attempt at the other

Select Case txtNbrSelections
Case 1
Call subCombo1 (txtMaxNbr)
Case 2
Call subCombo2 (txtMaxNbr)
.
.
.
Case Max
Call subComboMax (txtMaxNbr)
End Select

Combo1, Combo2, etc use the code from above to the approrpiate level.

mlmcc

0

Author Commented:
thanks again. i actually figured out a way to do it recursively...

sub createCombinations()

sampleSize = InputBox("Enter Number of Total Fields", "Number of Total Fields")

comboSize = InputBox("Enter Size of Combinations", "Size of Combinations")

Open App.path & "\" & "combinations_" & sampleSize & "C" & comboSize & ".txt" For Output As #1

currentString = ""

Call combine(currentString, sampleSize, comboSize, 1, 1)
Close #1

end sub

Sub combine(currentString As String, sampleSize As Integer, newComboSize As Integer, startPosition As Integer, fileNum As Integer)

Dim i As Integer

For i = startPosition To sampleSize - newComboSize + 1
If newComboSize = 1 Then 'end and print
Print #1, currentString & i
Else
Call combine(currentString & i & ",", sampleSize, newComboSize - 1, i + 1, 1)
End If
Next i

End Sub

I still have to find a way to get the file size smaller, but thanks for getting me going in the right direction originally and i'm accepting your comment as the answer.
0

Commented: