CODEWITHSUNDEEP
vb.netcombinationscombinatorics
MirrorMirror
MirrorMirror

Reputation: 188

combinations of words in arrays (or in a multidimensional array)

I have the following array:

array1(0,0) = "aaa "
array1(0,1) = "bbb "
array1(0,2) = "ccc "

array1(1,0) = "ddd "
array1(1,1) = "eee "

array1(2,0) = "fff "
array1(2,1) = "ggg "

I want to get all the following possible combinations:

aaa ddd fff
aaa ddd ggg
aaa eee fff
aaa eee ggg

bbb ddd fff
bbb ddd ggg
bbb eee fff
bbb eee ggg

ccc ddd fff
ccc ddd ggg
ccc eee fff
ccc eee ggg

the length of the array is dynamic in both dimensions, not only in the second, so a solution with 3 For loops inside each other doesn't apply. I'm working this in VB and off the top of my head I cannot see a way of how to go around this.

Which would be the best/fastest way to solve this ?

Thank you advance

Upvotes: 1

Views: 102

Answers (2)

Joseph Wood
Joseph Wood

Reputation: 7597

The OP is after the Cartesian product. As @the_lotus suggests, the OP should probably use a List here as you will have tighter controls over the length of each level in a given dimension. As it stands with arrays, we have to do a bit of loop gymnastics to find the length of each level.

Here is an algorithm that produces the cartestian product while avoiding generating intermediates (E.g. "aaa ", "aaa ddd ", etc.)

Dim array1(0 To 2, 0 To 2) As String, i As Long, j As Long
Dim myProd As Long, sizeDim() As Long, loopLim As Long, test As Long
Dim lenArr As Long, myCounter() As Long, myComb As String

array1(0, 0) = "aaa "
array1(0, 1) = "bbb "
array1(0, 2) = "ccc "

array1(1, 0) = "ddd "
array1(1, 1) = "eee "

array1(2, 0) = "fff "
array1(2, 1) = "ggg "

lenArr = UBound(array1, 1)
myProd = 1
ReDim sizeDim(0 To lenArr)

For j = 0 To lenArr
    test = UBound(array1, 2)

    '' Find the last non-empty entry
    Do While Len(array1(j, test) & vbNullString) = 0
        test = test - 1
    Loop

    myProd = myProd * (test + 1)
    sizeDim(j) = test
Next j

ReDim myCounter(0 To lenArr)
loopLim = myProd - 1
myComb = vbNullString

Dim cartProd() as String
Redim cartProd(0 to loopLim)

For i = 0 To loopLim - 1
    For j = 0 To lenArr
        myComb = myComb & array1(j, myCounter(j))
    Next j

    cartProd(i) = myComb
    Console.Writeline(myComb)

    test = 0
    Do While (myCounter(test) = sizeDim(test))
        myCounter(test) = 0
        test = test + 1
    Loop

    myCounter(test) = myCounter(test) + 1
    myComb = vbNullString
Next i

'' Get last result
For j = 0 To lenArr
    myComb = myComb & array1(j, myCounter(j))
Next j

cartProd(loopLim) = myComb
Console.Writeline(myComb)

And here is the output:

aaa ddd fff 
bbb ddd fff 
ccc ddd fff 
aaa eee fff 
bbb eee fff 
ccc eee fff 
aaa ddd ggg 
bbb ddd ggg 
ccc ddd ggg 
aaa eee ggg 
bbb eee ggg 
ccc eee ggg

Upvotes: 0

the_lotus
the_lotus

Reputation: 12748

Just keep a list of all sequences that you already did and just add the new one to all of the previous sequences.

    Dim allSequences As New List(Of String)

    allSequences.Add("")

    For x As Integer = 0 To allPossibilities.Count - 1
        Dim newSequences As New List(Of String)

        For y As Integer = 0 To allPossibilities(x).Count - 1
            For Each s As String In allSequences
                newSequences.Add(s & allPossibilities(x)(y))
            Next
        Next

        allSequences = newSequences
    Next

The variable allPossibilities is your array. I decided to use a list to make it easier for me. Using (,) wouldn't offer the same options as using ()().

        Dim allPossibilities As New List(Of List(Of String))

        allPossibilities.Add(New List(Of String))
        allPossibilities(0).Add("aaa")
        allPossibilities(0).Add("bbb")
        allPossibilities(0).Add("ccc")

        allPossibilities.Add(New List(Of String))
        allPossibilities(1).Add("ddd")
        allPossibilities(1).Add("eee")

        allPossibilities.Add(New List(Of String))
        allPossibilities(2).Add("fff")
        allPossibilities(2).Add("ggg")

Upvotes: 1

Related Questions