Создать все возможные перестановки строк

Question

Это моя проблема. Существует строка «Случай 1 V1: A, B, C ...». Слова «Случай 1 V1:» - являются постоянными, а переменные A, B, C - переменными. Значение моей строки может содержать много элементов, обычно три, иногда 4-6 элементов. Я не знаю, что порядок элементов означает одно время: «Случай 1 V1: A, B, C» второй раз «Случай 1 V1: B, A, C». Я хотел бы создать список со всеми возможными комбинациями строк. Есть ли простой способ создания всех комбинаций?

Answer 1

Как о:

public static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> items) 
{ 
    foreach (var item in items) 
    { 
     var head = new T[] { item }; 
     var tail = items.Except(head).ToList(); 
     var subLists = Permutations(tail); 
     if (subLists.Any()) 
     { 
      foreach (var subList in subLists) 
      { 
       yield return head.Concat(subList); 
      } 
     } 
     else 
     { 
      yield return head; 
     } 
    } 
} 

Ниже

foreach (var p in Permutations(new string[] { "A", "B", "C" })) 
{ 
    Console.WriteLine(string.Join(", ", p)); 
} 

дает

A, B, C 
A, C, B 
B, A, C 
B, C, A 
C, A, B 
C, B, A 

Обратите внимание, что это имеет сложность порядка п! где n - количество элементов в списке. Так что это нормально для трех предметов, но как только вы начинаете попадать в списки с 8 или более пунктами, есть десятки тысяч перестановок.

Как я сказал выше, я думаю, что было бы намного лучше, чем генерировать все варианты и тестировать их один за другим, чтобы посмотреть, что на самом деле есть, и посмотреть, соответствует ли оно тому, что вы ожидаете. Убедитесь, что список имеет ожидаемое количество элементов, а затем проверьте, не появляется ли где-нибудь в этом списке каждый ожидаемый элемент хотя бы один раз.

Answer 2

У меня был метод Permute, вокруг которого я приспособился к вашим потребностям.

Он выводит следующее, что я думаю, это то, что вы просили:

Case 1 V1: A, B, C 
Case 1 V1: A, C, B 
Case 1 V1: B, A, C 
Case 1 V1: B, C, A 
Case 1 V1: C, A, B 
Case 1 V1: C, B, A 

Вот код:

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Demo 
{ 
    internal class Program 
    { 
     private void run() 
     { 
      string prefix = "Case 1 V1: "; 
      string[] possibilities = {"A", "B", "C"}; 

      foreach (var permutation in Permute(possibilities)) 
       Console.WriteLine(prefix + string.Join(", ", permutation)); 
     } 

     public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> sequence) 
     { 
      return permute(sequence, sequence.Count()); 
     } 

     private static IEnumerable<IEnumerable<T>> permute<T>(IEnumerable<T> sequence, int count) 
     { 
      if (count == 0) 
      { 
       yield return new T[0]; 
      } 
      else 
      { 
       int startingElementIndex = 0; 

       foreach (T startingElement in sequence) 
       { 
        IEnumerable<T> remainingItems = allExcept(sequence, startingElementIndex); 

        foreach (IEnumerable<T> permutationOfRemainder in permute(remainingItems, count - 1)) 
         yield return (new [] { startingElement }).Concat(permutationOfRemainder); 

        ++startingElementIndex; 
       } 
      } 
     } 

     private static IEnumerable<T> allExcept<T>(IEnumerable<T> input, int indexToSkip) 
     { 
      int index = 0; 

      foreach (T item in input) 
      { 
       if (index != indexToSkip) 
        yield return item; 

       ++index; 
      } 
     } 

     private static void Main() 
     { 
      new Program().run(); 
     } 
    } 
} 

Answer 3

Вы можете использовать типичные ранга/unrank технику для перестановок (на самом деле, в вашем случае, вы хотите unrank только):

public static class Permutations { 
    public static BigInteger Count(int size) { 
     if (size < 0) 
     return 0; 

     BigInteger result = 1; 

     for (int i = 2; i <= size; ++i) 
     result *= i; 

     return result; 
    } 

    public static int[] Unrank(int size, BigInteger rank) { 
     if (size < 0) 
     throw new ArgumentOutOfRangeException("size", "size should not be negative."); 
     else if (rank < 0) 
     throw new ArgumentOutOfRangeException("rank", "size should not be negative."); 

     int[] digits = new int[size]; 

     for (int digit = 2; digit <= size; ++digit) { 
     BigInteger divisor = digit; 

     digits[size - digit] = (int) (rank % divisor); 

     if (digit < size) 
      rank /= divisor; 
     } 

     int[] permutation = new int[size]; 
     List<int> usedDigits = new List<int>(size); 

     for (int i = 0; i < size; ++i) 
     usedDigits.Add(0); 

     for (int i = 0; i < size; ++i) { 
     int v = usedDigits.IndexOf(0, 0); 

     for (int k = 0; k < digits[i]; ++k) 
      v = usedDigits.IndexOf(0, v + 1); 

     permutation[i] = v; 
     usedDigits[v] = 1; 
     } 

     return permutation; 
    } 
    } 

    ... 

     StringBuilder Sb = new StringBuilder(); 

     String data = "Case 1 V1: A, B, C"; 

     String[] items = data.Substring("Case 1 V1:".Length).Trim().Split(',').Select(x => x.Trim()).ToArray(); 

     for (int i = 0; i < (int) Permutations.Count(items.Length); ++i) { 
     if (Sb.Length > 0) 
      Sb.AppendLine(); 

     Sb.Append("Case 1 V1: "); 

     Boolean firstItem = true; 

     foreach (int j in Permutations.Unrank(items.Length, i)) { 
      if (!firstItem) 
      Sb.Append(", "); 

      firstItem = false; 

      Sb.Append(items[j]); 
     } 
     } 

     String result = Sb.ToString(); 

Выход

Case 1 V1: A, B, C 
Case 1 V1: A, C, B 
Case 1 V1: B, A, C 
Case 1 V1: B, C, A 
Case 1 V1: C, A, B 
Case 1 V1: C, B, A