?
Solved

Help Creating Combination Algorithm (Not Permutation!)

Posted on 2003-03-19
7
Medium Priority
?
374 Views
Last Modified: 2008-01-09
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
Comment
Question by:acsher3
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
7 Comments
 
LVL 101

Expert Comment

by:mlmcc
ID: 8171095
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 Comment

by:acsher3
ID: 8171322
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
 
LVL 101

Expert Comment

by:mlmcc
ID: 8171595
I haven't tried it, does it create duplicates?

mlmcc
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:acsher3
ID: 8185170
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
 
LVL 101

Accepted Solution

by:
mlmcc earned 300 total points
ID: 8185292
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 Comment

by:acsher3
ID: 8185312
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
 
LVL 101

Expert Comment

by:mlmcc
ID: 8185535
Glad to help

mlmcc
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Ready to improve network connectivity? Watch this webinar to learn how SD-WANs and a one-click instant connect tool can boost provisions, deployment, and management of your cloud connection.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Martin
Here are a few simple, working, games that you can use as-is or as the basis for your own games. Tic-Tac-Toe This is one of the simplest of all games.   The game allows for a choice of who goes first and keeps track of the number of wins for…
You can of course define an array to hold data that is of a particular type like an array of Strings to hold customer names or an array of Doubles to hold customer sales, but what do you do if you want to coordinate that data? This article describes…
Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
Show developers how to use a criteria form to limit the data that appears on an Access report. It is a common requirement that users can specify the criteria for a report at runtime. The easiest way to accomplish this is using a criteria form that a…
Suggested Courses
Course of the Month14 days, 1 hour left to enroll

801 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question