Android Code Snippet Unique combinations of m objects from a set of n

Discussion in 'Code Snippets' started by William Lancee, Nov 18, 2018.

  1. William Lancee

    William Lancee Member Licensed User

    I recently needed a fast combination algorithm. This one is not new, but works very well.

    Code:
    Sub Process_Globals
        
    Private combinations(10,5As List
    End Sub

    Sub Activity_Create(FirstTime As Boolean)
        
    Dim tnow As Long = DateTime.Now
        setupCombinations
        
    Log(DateTime.Now - tnow)
        
    'the combinations(n,m) matrix has now all the lists of unique subsets of size m from 1 to 9 items
        'where m = 1 to 4; this can be changed in the sub
        'log output is 13 to 20 milliseconds
        
        tnow = 
    DateTime.Now
        
    Dim s() As String = Array As String("a""b""x""y""z")  'this can be any vector of objects
        For Each v() As Int In combinations(5,3)
            
    'Log (v(0) & " " & v(1) & " " & v(2))  'index vector
            Dim sb As StringBuilder
            sb.initialize
            
    For Each i As Int In v
                sb.append(s(i))
            
    Next
            
    Log(sb.ToString)
        
    Next
        
    'log output lines are: abx    aby    abz    axy    axz    ayz    bxy    bxz    byz    xyz
        Log(DateTime.Now - tnow)
        
    'log output is less than 1 millisecond
    End Sub

    Sub setupCombinations
        
    For i = 1 To 9
            
    For j = 1 To 4
                
    Dim a As List: a.initialize
                combinations(i,j) = a
            
    Next
        
    Next

        
    For m = 1 To 9
            
    Dim mnum As Int = Power(2,m)-1
            
    For i = mnum To 0 Step -1
                
    Dim set As String = "000000000" & Bit.ToBinaryString(i)
                set = set.SubString(set.Length-m)
                
    Dim cntones As Int = 0
                
    Dim b As List: b.initialize
                
    For j = 0 To m-1
                    
    If set.SubString2(j,j+1) = "1" Then
                        cntones = cntones + 
    1
                        
    If cntones>4 Then Exit
                        b.Add(j)
                    
    End If
                
    Next
                
    If cntones>0 And cntones<5 Then
                    
    Dim v(cntones) As Int
                    
    For j = 0 To cntones-1
                        v(j) = b.Get(j)
                    
    Next
                    combinations(m, cntones).Add(v)
                
    End If
            
    Next
        
    Next
    End Sub
     
    Ohanian and hatzisn like this.
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice