Create all possible String permutations

Question

He is my problem. There is String "Case 1 V1: A, B, C...". Words "Case 1 V1:" - are permanent and A, B , C - are variables. Meaning my String might be contained of many elements, usually three, sometimes 4-6 elements. I don't know the order of elements meaning one time it would be "Case 1 V1: A, B, C" the second time "Case 1 V1: B, A, C". I would like to make List with all possible string combinations. Is there an easy way of creating all the combinations?

Answer 1

I happened to have a Permute method lying around which I adapted to your needs.

It outputs the following, which I think is what you were asking for:

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

Here's the code:

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 2

How about:

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;
        }
    }
}

The following

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

yields

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

Note that this has complexity in the order n! where n is the number of items in the list. So its fine for three items, but once you start getting into lists with 8 or more items there are tens of thousands of permutations.

As I said above, I think it would be much better, rather than generating all options and testing them one by one, to look at what's actually there and see if it matches what you expect. Check that the list has the expected number of items, and then check to see if somewhere in that list each expected item appears at least once.

Answer 3

You can use typical rank/unrank technic for permutations (actually, in your case, you want unrank only):

  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();

Output

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