数组（或多维数组）中的单词组合

Question

我有以下数组：

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 "

我想获得以下所有可能的组合：

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

数组的长度在两个维度上都是动态的，而不仅仅是在第二个维度上，因此在彼此内部包含 3 个 For 循环的解决方案不适用。我正在 VB 中处理这个问题，但我一时想不起来如何解决这个问题。

best/fastest 解决此问题的方法是什么？

提前致谢

Answer 1

只需保留一份您已经完成的所有序列的列表，然后将新序列添加到所有之前的序列中即可。

    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

变量 allPossibilities 是你的数组。我决定使用列表来简化我的操作。使用 (,) 不会提供与使用 ()() 相同的选项。

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

Answer 2

OP 在 Cartesian product 之后。正如@the_lotus 所建议的那样，OP 可能应该在此处使用 List 因为您将对给定维度中每个级别的长度进行更严格的控制。与数组一样，我们必须做一些循环体操来找到每个级别的长度。

这是一个生成笛卡尔积同时避免生成中间体的算法（例如 "aaa "、"aaa ddd " 等）

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)

这是输出：

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

数组（或多维数组）中的单词组合

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

vb.net

combinations

combinatorics