Combinatorics: Need to formulate and list combinations from multiple arrays to display mapping output

Question

I have a mapping program that maps versioned language-codes from one version to another. The program maps the codes correctly with one caveat, working with combination codes. I have parsed the mapping files and have gotten far enough as to structure arrays with the options per node and calculate the number of possibilities given the data.

Consider the following data:

CodeA translates to: Array(1,1) = "CodeB|CodeC|CodeD|"
                     Array(1,2) = "CodeE|"
                     Array(1,3) = "CodeF|CodeG|"

What this means is that CodeA translates to (CodeB or CodeC or CodeD) with codeE with (CodeF or CodeG)

The code first calculates the # of possibilites (above has 6) then dims an array to fit the resulted strings. I need the stored strings to be all combinations of the mapping, i.e.:

CodeB with CodeE with CodeF
CodeB with CodeE with CodeG
CodeC with CodeE with CodeF
CodeC with CodeE with CodeG
CodeD with CodeE with CodeF
CodeD with CodeE with CodeG

The code needs to work with all different sizes of arrays with multiple mappings. The above example is simple, but it can get more complicated, like this:

CodeA translates to: Array(1,1) = "CodeB|CodeC|CodeD|"
                     Array(1,2) = "CodeE|"
                     Array(1,3) = "CodeF|CodeG|"
                     Array(2,1) = "CodeH|"
                     Array(2,2) = "CodeI|CodeJ|"
                     Array(2,3) = "CodeK|CodeL|CodeM|CodeN|"
                     Array(2,4) = "CodeO|"
                     Array(3,1) = "CodeQ|"
                     Array(3,2) = "CodeR|CodeS|"

Which means CodeA translates to: ((CodeB or CodeC or CodeD) with CodeE with (CodeF or CodeG)) or (CodeH with (CodeI or CodeJ) with (CodeK or CodeL or CodeM or CodeN) with CodeO) or (CodeQ with (CodeR or CodeS)) --- 96 combinations

The program will already know the max first subscript, so the code would look something like:

for i = 1 to maxSubOne
    GET_COMBINATIONS(Array(i))
next i

Any suggestions?

No, I haven't solved the first example. As far as I've gotten is to calculate the amount of possibilities by looping through the subscripts and using: occ = occ * (Len(myArray(i, i2)) - Len(Replace(myArray(i, i2), "|", ""))) (accounting for 0 elsewhere) — Andrew Robinson
– Andrew Robinson, Commented Jul 18, 2013 at 18:49

Tim Williams · Accepted Answer · 2013-07-23 19:46:12Z

I think this works...

EDIT: updated Combine() to make it insensitive to the base of the arrays contained in the submitted collection and change Do-Loop for For-Next

Sub Tester()

    Dim arr(1 To 3, 1 To 4)
    arr(1, 1) = "CodeB|CodeC|CodeD|"
    arr(1, 2) = "CodeE|"
    arr(1, 3) = "CodeF|CodeG|"
    arr(2, 1) = "CodeH|"
    arr(2, 2) = "CodeI|CodeJ|"
    arr(2, 3) = "CodeK|CodeL|CodeM|CodeN|"
    arr(2, 4) = "CodeO|"
    arr(3, 1) = "CodeQ|"
    arr(3, 2) = "CodeR|CodeS|"

    DoCombinations arr

End Sub

Sub DoCombinations(arr As Variant)

Dim r As Long, c As Long
Dim nc As Long, nr As Long
Dim a
Dim col As Collection, col2 As New Collection
Dim final() As String, tmp

nr = UBound(arr, 1)
nc = UBound(arr, 2)

For r = 1 To nr 'loop through first dimension
    Set col = New Collection
    For c = 1 To nc
        tmp = arr(r, c)
        If Len(tmp) > 0 Then
            'remove any trailing "|"
            If Right(tmp, 1) = "|" Then
                tmp = Left(tmp, Len(tmp) - 1)
            End If
            col.Add Split(tmp, "|")
        End If
    Next c
    col2.Add Combine(col, "-")
Next r

'intermediate arrays
For Each a In col2
    Debug.Print "-----Intermediate-----"
    Debug.Print Join(a, vbLf)
Next a

final = Combine(col2 "-") 'final combination...
Debug.Print "-----Final-----"
Debug.Print Join(final, vbCrLf)

End Sub    

'create combinations from a collection of string arrays
Function Combine(col As Collection, SEP As String) As String()

    Dim rv() As String
    Dim pos() As Long, lengths() As Long, lbs() As Long, ubs() As Long
    Dim t As Long, i As Long, n As Long, ub As Long
    Dim numIn As Long, s As String, r As Long

    numIn = col.Count
    ReDim pos(1 To numIn)
    ReDim lbs(1 To numIn)
    ReDim ubs(1 To numIn)
    ReDim lengths(1 To numIn)
    t = 0
    For i = 1 To numIn  'calculate # of combinations, and cache bounds/lengths
        lbs(i) = LBound(col(i))
        ubs(i) = UBound(col(i))
        lengths(i) = (ubs(i) - lbs(i)) + 1
        pos(i) = lbs(i)
        t = IIf(t = 0, lengths(i), t * lengths(i))
    Next i
    ReDim rv(0 To t - 1) 'resize destination array

    For n = 0 To (t - 1)
        s = ""
        For i = 1 To numIn
            s = s & IIf(Len(s) > 0, SEP, "") & col(i)(pos(i)) 'build the string
        Next i
        rv(n) = s

        For i = numIn To 1 Step -1
            If pos(i) <> ubs(i) Then   'Not done all of this array yet...
                pos(i) = pos(i) + 1    'Increment array index
                For r = i + 1 To numIn 'Reset all the indexes
                    pos(r) = lbs(r)    '   of the later arrays
                Next r
                Exit For
            End If
        Next i
    Next n

    Combine = rv
End Function

Tim: Looks interesting! I will give it a few passes and let you know how it works. Thank you!
Tim, worked great! I didn't actually need the "Final" part, just the "intermediates". Thank you very much!

Collectives™ on Stack Overflow

Combinatorics: Need to formulate and list combinations from multiple arrays to display mapping output

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related