Как я могу сгенерировать все перестановки/комбинации из нескольких массивов?

Question

Моя цель проста, я пытаюсь создать список всех возможных комбинаций для продукта в базе данных.

Так, например; варианты продукта являются

• Вариант продукта: Цвет/значения: красный, зеленый, синий
Вариант
• продукта: Размер/Значения: Маленькие, Med, Большой, XL
Вариант
• продукта: Стиль/Ценности : Мужчины, Женщины

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

Small, Red, Mens 
Small, Green, Mens 
Small, Blue, Mens 
etc 

Мне нужна чтобы работать, передаю ли я 2,3,4 или 5 массивов.

Я провел довольно много исследований и наткнулся на следующие статьи, но не смог выполнить свою задачу.

Статьи я нашел следующие:

• How to Generate Combinations of Elements of a List<T> in .NET 4.0
• vb .net permutation of string. permutation or combination?

Answer 1

Адаптирование код из Eric Lippert's blog на декартовы произведения:

Private Function CartesianProduct(Of T)(ParamArray sequences As T()()) As T()() 

    ' base case: 
    Dim result As IEnumerable(Of T()) = {New T() {}} 
    For Each sequence As var In sequences 
     Dim s = sequence 
     ' don't close over the loop variable 
     ' recursive case: use SelectMany to build the new product out of the old one 
     result = From seq In result 
       From item In s 
       Select seq.Concat({item}).ToArray() 
    Next 
    Return result.ToArray() 
End Function 

Использование:

Dim s1 As String() = New String() {"small", "med", "large", "XL"} 
Dim s2 As String() = New String() {"red", "green", "blue"} 
Dim s3 As String() = New String() {"Men", "Women"} 

Dim ss As String()() = CartesianProduct(s1, s2, s3) 

Answer 2

Три петли внутри друг друга должны делать трюк.

Так псевдокод ...

For each value in sex array 
    For each value in size array 
     For each value in colour array 
      Output sex, size, colour values 
     Next colour 
    Next size 
Next sex 

Обновлено Psudo

Sub ouputOptions(array1, array2, array3, array4, array5) 
    For each value in array1 
     For each value in array2 
      If array3 Not Nothing Then 
       For each value in array3 
        If array4 Not Nothing Then 
         For each value in array4 
          If array5 Not Nothing Then 
           For each value in array5 
            output array1, array2, array3, array4, array5 values 
           next array5 
          Else 
           Output array1, array2, array3, array4 values 
          End if 
         Next array4 
        Else 
         Output array1, array2, array3 values 
        End if 
       next array3 
      Else 
       Output array1, array2 values 
      End if 
     Next array2 
    Next array1 
End Sub 

Вы должны указать array3 до 5, как Факультативным

Answer 3

Вы можете добиться этого с небольшим количеством рекурсии.

После этого возвращается массив массивов строк.

Public class Permuter 

    Public Function Permute(ParamArray toPermute As String()()) As String()() 

     Return DoPermute(Nothing, toPermute) 

    End Function 

    ''' <summary> 
    ''' Permute the first two arrays,then pass that, and the remainder recursively 
    ''' </summary> 
    Private Function DoPermute(working As String()(), toPermute As String()()) As String()() 

     Dim nextWorking As String()() 

     If working Is Nothing Then 

      'Make a new working list 
      nextWorking = (From a In toPermute(0) 
         Select {a}).ToArray 

     Else 

      'Combine from the next working list 
      nextWorking = (From a In working, b In toPermute(0) 
          Select a.Concat({b}).ToArray).ToArray 

     End If 

     If toPermute.Length > 1 Then 

      'Go Around again 

      Dim nextPermute = toPermute.Skip(1).ToArray 

      Return DoPermute(nextWorking, nextPermute) 

     Else 

      'We're done 
      Return nextWorking 

     End If 

    End Function 

End Class 

Вызов общественности метод, как:

Dim permuter = New Permuter 
Dim permutations = permuter.Permute({"a", "b", "c"}, {"1", "2", "3"}, {"x", "y", "z"}) 

Обновление: Принимая на @ ссылки в блоге Эрик Липперт DStanley, в следующее преобразование метода аккумулятора упомянута на that post:

Public Function CartesianProduct(Of T)(ParamArray sequences As T()()) As IEnumerable(Of IEnumerable(Of T)) 

    Dim emptyProduct As IEnumerable(Of IEnumerable(Of T)) = {Enumerable.Empty(Of T)()} 

    Return sequences.Aggregate(
      emptyProduct, 
      Function(accumulator, sequence) _ 
       From accseq In accumulator, item In sequence 
       Select accseq.Concat({item}) 
     ) 

End Function 

Обратите внимание, что это возвращает ленивые запросы, а не расширенный набор массивов.

Answer 4

Рекурсия - это иногда неправильный путь.

Если вы не хотите использовать рекурсию (? Боясь исключений StackOverflow), вы можете сделать это следующим образом:

List<List<string>> Combine(List<List<string>> lists) 
{ 
    List<List<string>> result = new List<List<string>>(); 
    var arrayIndexes = new int[lists.Count]; 
    result.Add(GetCurrentItem(lists, arrayIndexes)); 
    while (!AllIndexesAreLast(lists, arrayIndexes)) 
    { 
     for (int i = arrayIndexes.Length - 1; i >= 0; i--) 
     { 
      arrayIndexes[i] = (arrayIndexes[i] + 1) % lists[i].Count; 
      if (arrayIndexes[i] != 0) 
      { 
       break; 
      } 
     } 
     result.Add(GetCurrentItem(lists, arrayIndexes)); 
    } 

    return result; 
} 

List<string> GetCurrentItem(List<List<string>> lists, int[] arrayIndexes) 
{ 
    var item = new List<string>(); 
    for (int i = 0; i < lists.Count; i++) 
    { 
     item.Add(lists[i][arrayIndexes[i]]); 
    } 
    return item; 
} 

bool AllIndexesAreLast(List<List<string>> lists, int[] arrayIndexes) 
{ 
    for (int i = 0; i < arrayIndexes.Length; i++) 
    { 
     if (lists[i].Count - 1 != arrayIndexes[i]) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

И вы можете использовать его как это:

var shirts = new List<List<string>>() 
{ 
    new List<string>() {"colour", "red", "blue", "green", "yellow"}, 
    new List<string>() {"cloth", "cotton", "poly", "silk"}, 
    new List<string>() {"type", "full", "half"} 
}; 
var result = Combine(shirts); 

Answer 5

(Я думаю), мне нужно было то же самое, но я не мог найти то, что мне нужно, среди ответов (в основном потому, что они были на незнакомых языках, я думаю).

Я пришел с этим (сама функция):

Public Function nChooseK(Of T)(ByVal Values As List(Of T), ByVal k As Integer, Optional ByRef Result As List(Of List(Of T)) = Nothing, Optional ByRef CurCombination As List(Of T) = Nothing, Optional ByVal Offset As Integer = 0) As List(Of List(Of T)) 
    Dim n = Values.Count 
    If CurCombination Is Nothing Then CurCombination = New List(Of T) 
    If Result Is Nothing Then Result = New List(Of List(Of T)) 

    If k <= 0 Then 
     Result.Add(CurCombination.ToArray.ToList) 
     Return Result 
    Else 
     For i = Offset To n - k 
      CurCombination.Add(Values(i)) 
      nChooseK(Values, k - 1, Result, CurCombination, i + 1) 
      CurCombination.RemoveAt(CurCombination.Count - 1) 
     Next 

     Return Result 
    End If 

End Function 

Все, что нужно сделать, это положить его в модуле (или чуть выше/ниже суб/функции, которая называет это я думаю) и вызов это с какой-либо переменной и числа

Как назвать:

nChooseK(List, kInteger) 

Небольшой пример:

Dim NumbersCombinations As List(Of List(Of Integer)) = nChooseK(lstNumbers, k) 

Полный пример для использования с Целыми и струнными инструментами наряду с печатью результата на экран:

 Dim Numbers() As Integer = {1, 2, 3, 4, 5} 
    Dim lstNumbers = New List(Of Integer) 
    Dim k = 3 
    lstNumbers.AddRange(Numbers) 

    Dim NumbersCombinations As List(Of List(Of Integer)) = nChooseK(lstNumbers, k) 

    Dim sbCombinations1 As New StringBuilder 
    For i = 0 To NumbersCombinations.Count - 1 
     sbCombinations1.AppendLine() 
     For j = 0 To NumbersCombinations(i).Count - 1 
      sbCombinations1.Append(NumbersCombinations(i)(j) & " ") 
     Next 
     sbCombinations1.Length = sbCombinations1.Length - 1 
    Next 
    MsgBox(sbCombinations1.ToString) 



    Dim lstNoumera = New List(Of String) 
    lstNoumera.AddRange({"ena", "dio", "tria", "tessera", "pente"}) 

    Dim Combinations As List(Of List(Of String)) = nChooseK(lstNoumera, k) 

    Dim sbCombinations2 As New StringBuilder 
    For i = 0 To Combinations.Count - 1 
     sbCombinations2.AppendLine() 
     For j = 0 To Combinations(i).Count - 1 
      sbCombinations2.Append(Combinations(i)(j) & " ") 
     Next 
     sbCombinations2.Length = sbCombinations2.Length - 1 
    Next 
    MsgBox(sbCombinations2.ToString)