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
  • Last Modified:

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
Asked:
acsher3
  • 4
  • 3
1 Solution
 
mlmccCommented:
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
 
acsher3Author 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
 
mlmccCommented:
I haven't tried it, does it create duplicates?

mlmcc
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
acsher3Author 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
 
mlmccCommented:
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
 
acsher3Author 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
 
mlmccCommented:
Glad to help

mlmcc
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now