Help Creating Combination Algorithm (Not Permutation!)
Posted on 2003-03-19
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
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.