-
Jan 27th, 2014, 09:16 AM
#1
Thread Starter
New Member
Combination Picker
Hello
Lively member Passel advised me this side of the vbforums. So here I am. He already gave me some stuff to think about. I wonder if I could get some other input over here.
Can you help me in about the subject of combinations. I'm searching for an algorithm that establishes which digits (natural number) correspond to a specific position (index) in a given combination. To be more specific. I have a (randomly picked) combination (no permutations) environment of 3 digits between 1 and 20. Index #1 will is {1,2,3}, Index #2 is {1,2,4},... and Index #1140 is {18,19,20}. Other combination environments will result in other combinations. To do away with the (time consuming) running through nested loops I was wondering I some could think of a system that allows me to build a function with three parameters, in this case (3,20,77) that would return a set of digits index #77={1,5,6}. Other parameter sets could be (5,50,index), (8,60,index), (2,10,index),...
My current coded version of the thing is a eight bit, three legged turtle (if you get my drift). I'm still figuring out some of the code improvements passel suggested.
Anyone interested? Thanks.
- Initial thread is situated in VBFORUMS/GENERAL/CODE IT BETTER/COMBINATION PICKER (?751835-Combination-Picker&p=4601751#post4601751)
-
Jan 27th, 2014, 07:20 PM
#2
New Member
Re: Combination Picker
Hi there!
I love this kind of puzzle and i will try to help you out with this one.
So, you want to retrieve the #-nth item in a big collection containing all the combinations of k-items among {1..m}, created assuming a sort of numeric ascending order. For the sake of simplicity let's assume k=2 and m=5 and you want the 5-th element which should be {2,3}. Now lets try to give a form to our structure. Think about the rows, like the first member in the set, and the columns like the other one. Here is how that should appear.
1#1,2 |
2#1,3 |
3#1,4 |
4#1,5 |
5#2,3 |
6#2,4 |
7#2,5 |
8#3,4 |
9#3,5 |
10#4,5 |
As you can see, your matter here is to get row and column indexes of the n-th element in the table, since the row index gives the first number and (column index + row index) gives you the second one.
I swear such a function to get them exists. We just need to generalize it to work on k-dimensions structure.
(For k=3 we can think to a tetrahedron!)
-
Jan 28th, 2014, 10:38 AM
#3
Re: Combination Picker
It's something like a reverse CartesianProduct. Given the index return the coordinates.
I recently wrote some routines based on some Java samples on StackOverflow
The most elegant version is the recursive version, but the Non-Recursive function holds the key to get the element-ids for a given index.
Code:
Public Type tpStringArray
lNofItems As Long
aData() As String
End Type
Public Function CartesianProduct(tA() As tpStringArray, sJoinVar As String) As String()
Dim aProduct() As String
Dim aResultSet() As String, lResultIndex As Long
Dim lSize As Long, i As Long, lCnt As Long
lSize = 1
For i = 0 To UBound(tA)
lSize = lSize * tA(i).lNofItems
Next i
ReDim aResultSet(lSize - 1)
ReDim aProduct(UBound(tA))
pCartesianProductRecursive tA, 0, aProduct, sJoinVar, aResultSet, lResultIndex, lCnt
CartesianProduct = aResultSet
End Function
Private Function pCartesianProductRecursive(tA() As tpStringArray, lDepth As Long, aProduct() As String, sJoinVar As String, aResultSet() As String, lResultIndex As Long, lCnt As Long)
Dim i As Long
For i = 0 To tA(lDepth).lNofItems - 1
lCnt = lCnt + 1
aProduct(lDepth) = tA(lDepth).aData(i)
If lDepth < UBound(tA) Then
pCartesianProductRecursive tA, lDepth + 1, aProduct, sJoinVar, aResultSet, lResultIndex, lCnt
Else
aResultSet(lResultIndex) = Join(aProduct, sJoinVar)
lResultIndex = lResultIndex + 1
End If
Next i
End Function
Private Function pCartesianProductNonRecursive(tStringArray() As tpStringArray, sJoinVar As String) As String()
Dim i As Long, j As Long
Dim lNofElements As Long, lNofItems() As Long
Dim lIndex As Long
Dim sProduct As String, aCartesionProduct() As String
Dim lUBound As Long
lUBound = UBound(tStringArray)
ReDim lNofItems(lUBound)
lNofElements = 1
For i = 0 To UBound(tStringArray)
lNofItems(i) = tStringArray(i).lNofItems
lNofElements = lNofElements * lNofItems(i)
Next i
ReDim aCartesionProduct(lNofElements - 1)
For i = 0 To lNofElements - 1
lIndex = i
sProduct = tStringArray(0).aData(lIndex Mod lNofItems(0))
lIndex = lIndex \ lNofItems(0)
For j = lUBound To 1 Step -1
sProduct = tStringArray(j).aData(lIndex Mod lNofItems(j)) & ("*" & sProduct)
lIndex = lIndex \ lNofItems(j)
Next j
aCartesionProduct(i) = sProduct
Next i
pCartesianProductNonRecursive = aCartesionProduct
End Function
Last edited by Arnoutdv; Jan 28th, 2014 at 10:48 AM.
-
Jan 28th, 2014, 10:47 AM
#4
Re: Combination Picker
Not tested, but this should work:
Code:
Public Type tpStringArray
lNofItems As Long
aData() As String
End Type
public Function CartesianIndexToElements(tStringArray() As tpStringArray, ByVal lIndex As Long) As String
Dim j As Long
Dim lElementIndex As Long
Dim sProduct As String
lElementIndex = lIndex
sProduct = CStr(lElementIndex Mod tStringArray(i).lNofItems(0))
lElementIndex = lElementIndex \ tStringArray(i).lNofItems(0)
For j = lUBound To 1 Step -1
sProduct = sProduct & "," & CStr(lElementIndex Mod tStringArray(i).lNofItems(j))
lElementIndex = lElementIndex \ tStringArray(i).lNofItems(j)
Next j
CartesianIndexToElements= sProduct
End Function
-
Jan 28th, 2014, 12:16 PM
#5
Re: Combination Picker
Arnoutdv, I'm just glancing at your code... are you coming up with the indexes or permutations or combinations? It seems like you're counting permutations, but the OP specified combinations:
combination (no permutations)
-
Jan 30th, 2014, 03:13 AM
#6
Thread Starter
New Member
Re: Combination Picker
Hi people
Thanks for showing interest in my problem. I'm inspired by your enthusiasm. Feel like home already.
+Spyke, I wonder if a table-like structure will do. You see, now we're talking of k=2 and k=3 but in reality k can be any number, although usually k will not be larger than 14. m may get as large as 50. The essential think in such a function remains speed.
-
Jan 30th, 2014, 05:53 AM
#7
Re: Combination Picker
@Lenggries, it seems to be called permutations.
Is the question about storing a multidimensional array in a single array and then retrieve the original indexes based on the single array index?
-
Jan 30th, 2014, 09:29 AM
#8
Thread Starter
New Member
Re: Combination Picker
+Arnoutdv, the purpose of the function is to return one set of digits in the form of an single array or string, based on k, m and the index. The program does not need to store the complete set of combinations for the given parameters k,m. This would be highly unpractical when numbers really run up high.
-
Feb 4th, 2014, 03:57 PM
#9
Re: Combination Picker
Hi JaZo, if I'm not mistaken, this Wikipedia article on Combinatorial Number Systems seems to deal with exactly the question you are asking. In particular, it says
Originally Posted by Wikipedia
The main application of the combinatorial number system is that it allows rapid computation of the k-combination that is at a given position in the lexicographic ordering, without having to explicitly list the k-combinations preceding it; this allows for instance random generation of k-combinations of a given set. Enumeration of k-combinations has many applications, among which software testing, sampling, quality control, and the analysis of lottery games.
BB
-
Feb 6th, 2014, 03:20 AM
#10
Re: Combination Picker
Originally Posted by boops boops
...if I'm not mistaken...
I agree, the question is exactly asking for an efficient algorithm to unrank an index to produce a k-combination. I imagine there's a fair amount of literature on the problem and its generalizations, but the greedy algorithm Wikipedia suggests is very straightforward to implement and seems reasonably fast, especially for the relatively small sizes of n and k here. You will need BigInt's (edit: you can use 64 bit longs through roughly combinations of {1, ..., 65}, but BigInts would be needed in general), and your indexes are slightly different from the article's, but that's all straightforward. It might be worthwhile to simply precompute and store the first (say) 50 rows of Pascal's triangle using the elementary recurrence rather than recomputing the relevant binomial coefficients every time.
Last edited by jemidiah; Feb 6th, 2014 at 03:23 AM.
The time you enjoy wasting is not wasted time.
Bertrand Russell
<- Remember to rate posts you find helpful.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|