Results 1 to 10 of 10

Thread: Combination Picker

  1. #1

    Thread Starter
    New Member
    Join Date
    Jan 2014
    Posts
    6

    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)

  2. #2
    New Member
    Join Date
    Dec 2013
    Posts
    5

    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!)

  3. #3
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    5,872

    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.

  4. #4
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    5,872

    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

  5. #5
    Hyperactive Member Lenggries's Avatar
    Join Date
    Sep 2009
    Posts
    353

    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)

  6. #6

    Thread Starter
    New Member
    Join Date
    Jan 2014
    Posts
    6

    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.

  7. #7
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    5,872

    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?

  8. #8

    Thread Starter
    New Member
    Join Date
    Jan 2014
    Posts
    6

    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.

  9. #9
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    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

    Quote 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

  10. #10
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Combination Picker

    Quote Originally Posted by boops boops View Post
    ...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
  •  



Click Here to Expand Forum to Full Width