Получить все перестановки списка (Of List (Of String)) в VB.NET

Question

У меня есть идея, что мою проблему можно решить с помощью рекурсивной функции, но, честно говоря, я не могу понять, с чего начать.

Начальная точка - это список (Of List (Of String)) :

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

Я хочу получить все комбинации для всех объектов List (Of String).

В качестве примера предположим, что 2 списка строк содержат следующие значения:

"a", "b", "c"    
"d", "e"    

Это должно привести к следующему:

"a d"
"a e"
"b d"
"b e"
"c d"
"c e"

Окончательный результат также может быть возвращен в форме List (Of String).

Я предполагаю, что реализация функции восстановления может работать, но у меня есть не знаю как реализовать:

Function createPermutations(ByVal Obj As List(Of List(Of String))) As List(Of String)

    Dim Result As New List(Of String)

    ...
    Result = createPermutations(...)
    ...

    Return Result

End Function

Answer 1

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
    Dim Obj As New List(Of List(Of String))

    Dim x As New List(Of String)
    x.Add("a")
    x.Add("b")
    x.Add("c")

    Dim y As New List(Of String)
    y.Add("d")
    y.Add("e")

    Obj.Add(x)
    Obj.Add(y)

    For Each outputString As String In createPermutations(0, Obj)
        System.Console.WriteLine(outputString)
    Next

End Sub

Function createPermutations(level As Integer, listOfLists As List(Of List(Of String)))
    Dim retval As New List(Of String)

    If (level = listOfLists.Count) Then
        retval.Add("")
        Return retval
    End If

    For Each y As String In listOfLists(level)
        For Each x2 As String In createPermutations(level + 1, listOfLists)
            retval.Add(y + " " + x2)
        Next
    Next
    Return retval
End Function

Answer 2

Вот нерекурсивное решение, которое может обрабатывать любое количество наборов, где каждый набор имеет переменное количество элементов:

Sub Main()
    Dim input As New List(Of List(Of String)) From {
        New List(Of String) From {"a", "b", "c"},
        New List(Of String) From {"d", "e"},
        New List(Of String) From {"f", "g", "h", "i"}
    }

    For Each combination In CartesianProducts(input)
        Console.WriteLine(String.Join(",", combination))
    Next

    Console.Write("Press Enter to quit...")
    Console.ReadLine()
End Sub

Public Iterator Function CartesianProducts(ByVal setList As List(Of List(Of String))) As IEnumerable(Of IEnumerable(Of String))
    Dim curIndex(setList.Count - 1) As Integer ' tells which item is currently being used from each set
    Dim setSizes = setList.Select(Function(curSet) curSet.Count) ' tells the number of items in each set
    Dim numCombinations As Integer = setSizes.Aggregate(Function(a, b) a * b) ' alls the sizes multiplied together

    For i As Integer = 1 To numCombinations
        ' return the current combination by gathering all the elements from each set using "curIndex"
        Yield Enumerable.Range(0, curIndex.Count).Select(Function(x) setList(x)(curIndex(x)))

        ' working backwards, increment the index in each slot
        ' if the new number equals the set size, reset to zero ...
        ' ...and let the loop continue, which will increment the index to the left
        ' if the new number was less than size for that set, simply exit the loop as you're done
        For j As Integer = curIndex.Count - 1 To 0 Step -1
            curIndex(j) = curIndex(j) + 1
            If curIndex(j) = setSizes(j) Then
                curIndex(j) = 0
            Else
                Exit For
            End If
        Next
    Next
End Function

Вывод:

a,d,f
a,d,g
a,d,h
a,d,i
a,e,f
a,e,g
a,e,h
a,e,i
b,d,f
b,d,g
b,d,h
b,d,i
b,e,f
b,e,g
b,e,h
b,e,i
c,d,f
c,d,g
c,d,h
c,d,i
c,e,f
c,e,g
c,e,h
c,e,i
Press Enter to quit...

Вот визуальный представление того, что делает массив curIndex:

[ 0,0,0 ]
[ 0,0,1 ]
[ 0,0,2 ]
[ 0,0,3 ]
[ 0,1,0 ]
[ 0,1,1 ]
[ 0,1,2 ]
[ 0,1,3 ]
[ 1,0,0 ]
[ 1,0,1 ]
[ 1,0,2 ]
[ 1,0,3 ]
[ 1,1,0 ]
[ 1,1,1 ]
[ 1,1,2 ]
[ 1,1,3 ]
[ 2,0,0 ]
[ 2,0,1 ]
[ 2,0,2 ]
[ 2,0,3 ]
[ 2,1,0 ]
[ 2,1,1 ]
[ 2,1,2 ]
[ 2,1,3 ]

Answer 3

Как насчет использования двух циклов, внутреннего и внешнего, например,

Function createPermutations(ByVal Obj As List(Of List(Of String))) As List(Of String)

        Dim Result As New List(Of String)

        Dim list_1 As New List(Of String)
        Dim list_2 As New List(Of String)


        For Each itemL1 In list_1
            For Each itemL2 In list_2
                Result.Add(itemL1 & " " & itemL2)

            Next

        Next
    

        Return Result

    End Function