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

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

B4X:
Sub Process_Globals
    Private combinations(10,5) As 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
 
Top