Перечисление всех перестановок строки / целого числа

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

Есть ли пример того, как это делается, и логика решения такой проблемы?

Я видел несколько фрагментов кода, но они не были хорошо прокомментированы / объяснены и, следовательно, трудны для понимания.

Прежде всего: конечно, пахнет рекурсией !

Поскольку вы также хотели знать этот принцип, я приложил все усилия, чтобы объяснить его на человеческом языке. Я думаю, что рекурсия в большинстве случаев очень проста. Вам нужно только понять два шага:

1. Первый шаг
2. Все остальные шаги (все с той же логикой)

На человеческом языке :

Вкратце:
1. Перестановка 1 элемента - это один элемент.
2. Перестановка набора элементов представляет собой список каждого из элементов, соединенных с каждой перестановкой других элементов.

Пример:

Если в наборе только один элемент ->
вернуть его.
Пермь (а) -> а

Если в наборе есть два символа: для каждого элемента в нем: вернуть элемент с перестановкой остальных добавленных элементов, например:

Пермь (ab) ->

a + perm (b) -> ab

б + пермь (а) -> ба

Далее: для каждого символа в наборе: вернуть символ, объединенный с пермумацией> остальной части набора

Пермь (abc) ->

a + perm (bc) -> abc , acb

b + perm (ac) -> bac , bca

c + perm (ab) -> такси , cba

Пермь (abc ... z) ->

а + перми (...), б + перми (....)
....

Я нашел псевдокод на http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/ :

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation+i)
      }
    }
  }
  else {
    add permutation to list
  }
}

C #

Хорошо, и что-то более сложное (и так как он помечен c #), от http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : довольно долго, но я решил скопировать его во всяком случае, поэтому пост не зависит от оригинала.

Функция принимает строку символов и записывает каждую возможную перестановку этой точной строки, поэтому, например, если было указано «ABC», должно появиться:

ABC, ACB, BAC, BCA, CAB, CBA.

Код:

class Program
{
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        var temp = a;
        a = b;
        b = temp;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            Console.Write(list);
        }
        else
            for (int i = k; i <= m; i++)
            {
                   Swap(ref list[k], ref list[i]);
                   GetPer(list, k + 1, m);
                   Swap(ref list[k], ref list[i]);
            }
    }

    static void Main()
    {
        string str = "sagiv";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}

Это всего лишь две строки кода, если LINQ разрешено использовать. Пожалуйста, посмотрите мой ответ здесь .

РЕДАКТИРОВАТЬ

Вот моя общая функция, которая может возвращать все перестановки (не комбинации) из списка T:

static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Пример:

IEnumerable<IEnumerable<int>> result =
    GetPermutations(Enumerable.Range(1, 3), 3);

Вывод - список целочисленных списков:

{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

Поскольку эта функция использует LINQ, для нее требуется .net 3.5 или выше.

Здесь я нашел решение. Он был написан на Java, но я преобразовал его в C #. Я надеюсь, что это поможет вам.

Вот код в C #:

static void Main(string[] args)
{
    string str = "ABC";
    char[] charArry = str.ToCharArray();
    Permute(charArry, 0, 2);
    Console.ReadKey();
}

static void Permute(char[] arry, int i, int n)
{
    int j;
    if (i==n)
        Console.WriteLine(arry);
    else
    {
        for(j = i; j <=n; j++)
        {
            Swap(ref arry[i],ref arry[j]);
            Permute(arry,i+1,n);
            Swap(ref arry[i], ref arry[j]); //backtrack
        }
    }
}

static void Swap(ref char a, ref char b)
{
    char tmp;
    tmp = a;
    a=b;
    b = tmp;
}

Рекурсия не нужна, вот хорошая информация об этом решении.

var values1 = new[] { 1, 2, 3, 4, 5 };

foreach (var permutation in values1.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

var values2 = new[] { 'a', 'b', 'c', 'd', 'e' };

foreach (var permutation in values2.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Console.ReadLine();

Я использовал этот алгоритм в течение многих лет, он имеет O (N) сложность времени и пространства для расчета каждой перестановки .

public static class SomeExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
    {
        var array = enumerable as T[] ?? enumerable.ToArray();

        var factorials = Enumerable.Range(0, array.Length + 1)
            .Select(Factorial)
            .ToArray();

        for (var i = 0L; i < factorials[array.Length]; i++)
        {
            var sequence = GenerateSequence(i, array.Length - 1, factorials);

            yield return GeneratePermutation(array, sequence);
        }
    }

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
    {
        var clone = (T[]) array.Clone();

        for (int i = 0; i < clone.Length - 1; i++)
        {
            Swap(ref clone[i], ref clone[i + sequence[i]]);
        }

        return clone;
    }

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
    {
        var sequence = new int[size];

        for (var j = 0; j < sequence.Length; j++)
        {
            var facto = factorials[sequence.Length - j];

            sequence[j] = (int)(number / facto);
            number = (int)(number % facto);
        }

        return sequence;
    }

    static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    private static long Factorial(int n)
    {
        long result = n;

        for (int i = 1; i < n; i++)
        {
            result = result * i;
        }

        return result;
    }
}

void permute (char *str, int ptr) {
  int i, len;
  len = strlen(str);
  if (ptr == len) {
    printf ("%s\n", str);
    return;
  }

  for (i = ptr ; i < len ; i++) {
    swap (&str[ptr], &str[i]);
    permute (str, ptr + 1);
    swap (&str[ptr], &str[i]);
  }
}

Вы можете написать свою функцию подкачки, чтобы поменять символы.
Это должно называться permute (string, 0);

Прежде всего, наборы имеют перестановки, а не строки или целые числа, поэтому я просто предположу, что вы имеете в виду «набор символов в строке».

Обратите внимание, что набор размера n имеет n! п-перестановки.

Следующий псевдокод (из Википедии), вызываемый с k = 1 ... n! даст все перестановки:

function permutation(k, s) {
    for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j; // integer division cuts off the remainder
    }
    return s;
}

Вот эквивалентный код Python (для индексов массива на основе 0):

def permutation(k, s):
    r = s[:]
    for j in range(2, len(s)+1):
        r[j-1], r[k%j] = r[k%j], r[j-1]
        k = k/j+1
    return r

Слегка измененная версия в C #, которая дает необходимые перестановки в массиве ЛЮБОГО типа.

    // USAGE: create an array of any type, and call Permutations()
    var vals = new[] {"a", "bb", "ccc"};
    foreach (var v in Permutations(vals))
        Console.WriteLine(string.Join(",", v)); // Print values separated by comma


public static IEnumerable<T[]> Permutations<T>(T[] values, int fromInd = 0)
{
    if (fromInd + 1 == values.Length)
        yield return values;
    else
    {
        foreach (var v in Permutations(values, fromInd + 1))
            yield return v;

        for (var i = fromInd + 1; i < values.Length; i++)
        {
            SwapValues(values, fromInd, i);
            foreach (var v in Permutations(values, fromInd + 1))
                yield return v;
            SwapValues(values, fromInd, i);
        }
    }
}

private static void SwapValues<T>(T[] values, int pos1, int pos2)
{
    if (pos1 != pos2)
    {
        T tmp = values[pos1];
        values[pos1] = values[pos2];
        values[pos2] = tmp;
    }
}

class Program
{
    public static void Main(string[] args)
    {
        Permutation("abc");
    }

    static void Permutation(string rest, string prefix = "")
    {
        if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);

        // Each letter has a chance to be permutated
        for (int i = 0; i < rest.Length; i++)
        {                
            Permutation(rest.Remove(i, 1), prefix + rest[i]);
        }
    }
}

Мне понравился подход FBryant87, поскольку он прост. К сожалению, он, как и многие другие «решения», не предлагает все перестановки или, например, целое число, если он содержит одну и ту же цифру более одного раза. Возьмите 656123 в качестве примера. Линия:

var tail = chars.Except(new List<char>(){c});

используя Кроме причинит все случаи должны быть удалены, то есть , когда с = 6, две цифры удаляются , и мы остались с , например , 5123. Поскольку ни один из решений я пытался решить это, я решил попробовать и решить сам по FBryant87 «с код в качестве базы. Вот что я придумал:

private static List<string> FindPermutations(string set)
    {
        var output = new List<string>();
        if (set.Length == 1)
        {
            output.Add(set);
        }
        else
        {
            foreach (var c in set)
            {
                // Remove one occurrence of the char (not all)
                var tail = set.Remove(set.IndexOf(c), 1);
                foreach (var tailPerms in FindPermutations(tail))
                {
                    output.Add(c + tailPerms);
                }
            }
        }
        return output;
    }

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

Однако следует отметить одну вещь: результирующий список может содержать дубликаты, поэтому убедитесь, что вы либо заставили метод вернуть, например, HashSet, либо удалили дубликаты после возврата, используя любой понравившийся метод.

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

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

C ++ и Python имеют встроенные функции next_permutation и itertools.permutations соответственно.

Вот чисто функциональная реализация F #:

let factorial i =
    let rec fact n x =
        match n with
        | 0 -> 1
        | 1 -> x
        | _ -> fact (n-1) (x*n)
    fact i 1

let swap (arr:'a array) i j = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]

let rec permutation (k:int,j:int) (r:'a array) =
    if j = (r.Length + 1) then r
    else permutation (k/j+1, j+1) (swap r (j-1) (k%j))

let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source }

Производительность может быть значительно улучшена путем изменения подкачки, чтобы воспользоваться изменчивой природой массивов CLR, но эта реализация является поточно-ориентированной по отношению к исходному массиву, и это может быть желательно в некоторых контекстах. Кроме того, для массивов с более чем 16 элементами int необходимо заменить на типы с большей / произвольной точностью, поскольку факториал 17 приводит к переполнению int32.

Вот простое решение в C # с использованием рекурсии,

void Main()
{
    string word = "abc";
    WordPermuatation("",word);
}

void WordPermuatation(string prefix, string word)
{
    int n = word.Length;
    if (n == 0) { Console.WriteLine(prefix); }
    else
    {
        for (int i = 0; i < n; i++)
        {
            WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1)));
        }
    }
}

Вот простая для понимания функция перестановки для строки и целого числа в качестве входных данных. При этом вы даже можете установить свою выходную длину (которая в нормальном случае равна длине ввода)

строка

    static ICollection<string> result;

    public static ICollection<string> GetAllPermutations(string str, int outputLength)
    {
        result = new List<string>();
        MakePermutations(str.ToCharArray(), string.Empty, outputLength);
        return result;
    }

    private static void MakePermutations(
       char[] possibleArray,//all chars extracted from input
       string permutation,
       int outputLength//the length of output)
    {
         if (permutation.Length < outputLength)
         {
             for (int i = 0; i < possibleArray.Length; i++)
             {
                 var tempList = possibleArray.ToList<char>();
                 tempList.RemoveAt(i);
                 MakePermutations(tempList.ToArray(), 
                      string.Concat(permutation, possibleArray[i]), outputLength);
             }
         }
         else if (!result.Contains(permutation))
            result.Add(permutation);
    }

а для Integer просто измените метод вызывающей стороны, и MakePermutations () останется нетронутым:

    public static ICollection<int> GetAllPermutations(int input, int outputLength)
    {
        result = new List<string>();
        MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength);
        return result.Select(m => int.Parse(m)).ToList<int>();
    }

пример 1: GetAllPermutations ("abc", 3); "abc" "acb" "bac" "bca" "cab" "cba"

пример 2: GetAllPermutations ("abcd", 2); "ab" "ac" "ad" "ba" "bc" "bd" "ca" "cb" "cd" "da" "db" "dc"

пример 3: GetAllPermutations (486,2); 48 46 84 86 64 68

Вот функция, которая будет печатать все перестановки. Эта функция реализует логику, объясненную Петром.

public class Permutation
{
    //http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm

    public static void permuteString(String beginningString, String endingString)
    {           

        if (endingString.Length <= 1)
            Console.WriteLine(beginningString + endingString);
        else
            for (int i = 0; i < endingString.Length; i++)
            {

                String newString = endingString.Substring(0, i) + endingString.Substring(i + 1);

                permuteString(beginningString + endingString.ElementAt(i), newString);

            }
    }
}

    static void Main(string[] args)
    {

        Permutation.permuteString(String.Empty, "abc");
        Console.ReadLine();

    }

Ниже моя реализация перестановки. Не обращайте внимания на имена переменных, так как я делал это для удовольствия :)

class combinations
{
    static void Main()
    {

        string choice = "y";
        do
        {
            try
            {
                Console.WriteLine("Enter word :");
                string abc = Console.ReadLine().ToString();
                Console.WriteLine("Combinatins for word :");
                List<string> final = comb(abc);
                int count = 1;
                foreach (string s in final)
                {
                    Console.WriteLine("{0} --> {1}", count++, s);
                }
                Console.WriteLine("Do you wish to continue(y/n)?");
                choice = Console.ReadLine().ToString();
            }
            catch (Exception exc)
            {
                Console.WriteLine(exc);
            }
        } while (choice == "y" || choice == "Y");
    }

    static string swap(string test)
    {
        return swap(0, 1, test);
    }

    static List<string> comb(string test)
    {
        List<string> sec = new List<string>();
        List<string> first = new List<string>();
        if (test.Length == 1) first.Add(test);
        else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
        else if (test.Length > 2)
        {
            sec = generateWords(test);
            foreach (string s in sec)
            {
                string init = s.Substring(0, 1);
                string restOfbody = s.Substring(1, s.Length - 1);

                List<string> third = comb(restOfbody);
                foreach (string s1 in third)
                {
                    if (!first.Contains(init + s1)) first.Add(init + s1);
                }


            }
        }

        return first;
    }

    static string ShiftBack(string abc)
    {
        char[] arr = abc.ToCharArray();
        char temp = arr[0];
        string wrd = string.Empty;
        for (int i = 1; i < arr.Length; i++)
        {
            wrd += arr[i];
        }

        wrd += temp;
        return wrd;
    }

    static List<string> generateWords(string test)
    {
        List<string> final = new List<string>();
        if (test.Length == 1)
            final.Add(test);
        else
        {
            final.Add(test);
            string holdString = test;
            while (final.Count < test.Length)
            {
                holdString = ShiftBack(holdString);
                final.Add(holdString);
            }
        }

        return final;
    }

    static string swap(int currentPosition, int targetPosition, string temp)
    {
        char[] arr = temp.ToCharArray();
        char t = arr[currentPosition];
        arr[currentPosition] = arr[targetPosition];
        arr[targetPosition] = t;
        string word = string.Empty;
        for (int i = 0; i < arr.Length; i++)
        {
            word += arr[i];

        }

        return word;

    }
}

Вот пример высокого уровня, который я написал, который иллюстрирует объяснение на человеческом языке, которое дал Питер:

    public List<string> FindPermutations(string input)
    {
        if (input.Length == 1)
            return new List<string> { input };
        var perms = new List<string>();
        foreach (var c in input)
        {
            var others = input.Remove(input.IndexOf(c), 1);
            perms.AddRange(FindPermutations(others).Select(perm => c + perm));
        }
        return perms;
    }

Если производительность и память являются проблемой, я предлагаю эту очень эффективную реализацию. Согласно алгоритму Хипа в Википедии , он должен быть самым быстрым. Надеюсь, что это будет соответствовать вашим потребностям :-)!

Так же, как сравнение этого с реализацией Linq для 10! (код включен):

• Это: 36288000 предметов в 235 миллисекундах

• Linq: 36288000 наименований в 50051 миллисек

  using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.Linq;
  using System.Runtime.CompilerServices;
  using System.Text;
  
  namespace WpfPermutations
  {
      /// <summary>
      /// EO: 2016-04-14
      /// Generator of all permutations of an array of anything.
      /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
      /// </summary>
      public static class Permutations
      {
          /// <summary>
          /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
          /// </summary>
          /// <param name="items">Items to permute in each possible ways</param>
          /// <param name="funcExecuteAndTellIfShouldStop"></param>
          /// <returns>Return true if cancelled</returns> 
          public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
          {
              int countOfItem = items.Length;
  
              if (countOfItem <= 1)
              {
                  return funcExecuteAndTellIfShouldStop(items);
              }
  
              var indexes = new int[countOfItem];
              for (int i = 0; i < countOfItem; i++)
              {
                  indexes[i] = 0;
              }
  
              if (funcExecuteAndTellIfShouldStop(items))
              {
                  return true;
              }
  
              for (int i = 1; i < countOfItem;)
              {
                  if (indexes[i] < i)
                  { // On the web there is an implementation with a multiplication which should be less efficient.
                      if ((i & 1) == 1) // if (i % 2 == 1)  ... more efficient ??? At least the same.
                      {
                          Swap(ref items[i], ref items[indexes[i]]);
                      }
                      else
                      {
                          Swap(ref items[i], ref items[0]);
                      }
  
                      if (funcExecuteAndTellIfShouldStop(items))
                      {
                          return true;
                      }
  
                      indexes[i]++;
                      i = 1;
                  }
                  else
                  {
                      indexes[i++] = 0;
                  }
              }
  
              return false;
          }
  
          /// <summary>
          /// This function is to show a linq way but is far less efficient
          /// </summary>
          /// <typeparam name="T"></typeparam>
          /// <param name="list"></param>
          /// <param name="length"></param>
          /// <returns></returns>
          static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
          {
              if (length == 1) return list.Select(t => new T[] { t });
  
              return GetPermutations(list, length - 1)
                  .SelectMany(t => list.Where(e => !t.Contains(e)),
                      (t1, t2) => t1.Concat(new T[] { t2 }));
          }
  
          /// <summary>
          /// Swap 2 elements of same type
          /// </summary>
          /// <typeparam name="T"></typeparam>
          /// <param name="a"></param>
          /// <param name="b"></param>
          [MethodImpl(MethodImplOptions.AggressiveInlining)]
          static void Swap<T>(ref T a, ref T b)
          {
              T temp = a;
              a = b;
              b = temp;
          }
  
          /// <summary>
          /// Func to show how to call. It does a little test for an array of 4 items.
          /// </summary>
          public static void Test()
          {
              ForAllPermutation("123".ToCharArray(), (vals) =>
              {
                  Debug.Print(String.Join("", vals));
                  return false;
              });
  
              int[] values = new int[] { 0, 1, 2, 4 };
  
              Debug.Print("Non Linq");
              ForAllPermutation(values, (vals) =>
              {
                  Debug.Print(String.Join("", vals));
                  return false;
              });
  
              Debug.Print("Linq");
              foreach(var v in GetPermutations(values, values.Length))
              {
                  Debug.Print(String.Join("", v));
              }
  
              // Performance
              int count = 0;
  
              values = new int[10];
              for(int n = 0; n < values.Length; n++)
              {
                  values[n] = n;
              }
  
              Stopwatch stopWatch = new Stopwatch();
              stopWatch.Reset();
              stopWatch.Start();
  
              ForAllPermutation(values, (vals) =>
              {
                  foreach(var v in vals)
                  {
                      count++;
                  }
                  return false;
              });
  
              stopWatch.Stop();
              Debug.Print($"Non Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
  
              count = 0;
              stopWatch.Reset();
              stopWatch.Start();
  
              foreach (var vals in GetPermutations(values, values.Length))
              {
                  foreach (var v in vals)
                  {
                      count++;
                  }
              }
  
              stopWatch.Stop();
              Debug.Print($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
  
          }
      }
  }

Вот мое решение в JavaScript (NodeJS). Основная идея заключается в том, что мы берем один элемент за раз, «удаляем его» из строки, меняем остальные символы и вставляем элемент впереди.

function perms (string) {
  if (string.length == 0) {
    return [];
  }
  if (string.length == 1) {
    return [string];
  }
  var list = [];
  for(var i = 0; i < string.length; i++) {
    var invariant = string[i];
    var rest = string.substr(0, i) + string.substr(i + 1);
    var newPerms = perms(rest);
    for (var j = 0; j < newPerms.length; j++) {
      list.push(invariant + newPerms[j]);
    }
  }
  return list;
}

module.exports = perms;

А вот и тесты:

require('should');
var permutations = require('../src/perms');

describe('permutations', function () {
  it('should permute ""', function () {
    permutations('').should.eql([]);
  })

  it('should permute "1"', function () {
    permutations('1').should.eql(['1']);
  })

  it('should permute "12"', function () {
    permutations('12').should.eql(['12', '21']);
  })

  it('should permute "123"', function () {
    var expected = ['123', '132', '321', '213', '231', '312'];
    var actual = permutations('123');
    expected.forEach(function (e) {
      actual.should.containEql(e);
    })
  })

  it('should permute "1234"', function () {
    // Wolfram Alpha FTW!
    var expected = ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132'];
    var actual = permutations('1234');
    expected.forEach(function (e) {
      actual.should.containEql(e);
    })
  })
})

Вот самое простое решение, которое я могу придумать:

let rec distribute e = function
  | [] -> [[e]]
  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs

distributeФункция принимает новый элемент eи n-элементный список и возвращает список n+1списков , каждый из которых имеет eвставленные в другом месте. Например, вставляя 10в каждое из четырех возможных мест в списке [1;2;3]:

> distribute 10 [1..3];;
val it : int list list =
  [[10; 1; 2; 3]; [1; 10; 2; 3]; [1; 2; 10; 3]; [1; 2; 3; 10]]

permuteФункция складки над каждым элементом в своей очереди , распределяющий над перестановками , накопленных до сих пор, кульминация всех перестановок. Например, 6 перестановок в списке [1;2;3]:

> permute [1;2;3];;
val it : int list list =
  [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]

Изменение на folda scanдля сохранения промежуточных аккумуляторов проливает некоторый свет на то, как перестановки генерируются элементом за раз:

> Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];;
val it : seq<int list list> =
  seq
    [[[]]; [[1]]; [[2; 1]; [1; 2]];
     [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]]

Перечисляет перестановки строки. Избегает дублирования при повторении символов:

using System;
using System.Collections;

class Permutation{
  static IEnumerable Permutations(string word){
    if (word == null || word.Length <= 1) {
      yield return word;
      yield break;
    }

    char firstChar = word[0];
    foreach( string subPermute in Permutations (word.Substring (1)) ) {
      int indexOfFirstChar = subPermute.IndexOf (firstChar);
      if (indexOfFirstChar == -1) indexOfFirstChar = subPermute.Length;

      for( int index = 0; index <= indexOfFirstChar; index++ )
        yield return subPermute.Insert (index, new string (firstChar, 1));
    }
  }

  static void Main(){
    foreach( var permutation in Permutations ("aab") )
      Console.WriteLine (permutation);
  }
}

Основываясь на решении @ Peter, вот версия, которая объявляет простой Permutations()метод расширения в стиле LINQ, который работает на любом IEnumerable<T>.

Использование (на примере строковых символов):

foreach (var permutation in "abc".Permutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Выходы:

a, b, c
a, c, b
b, a, c
b, c, a
c, b, a
c, a, b

Или на любой другой тип коллекции:

foreach (var permutation in (new[] { "Apples", "Oranges", "Pears"}).Permutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Выходы:

Apples, Oranges, Pears
Apples, Pears, Oranges
Oranges, Apples, Pears
Oranges, Pears, Apples
Pears, Oranges, Apples
Pears, Apples, Oranges

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

public static class PermutationExtension
{
    public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> source)
    {
        var sourceArray = source.ToArray();
        var results = new List<T[]>();
        Permute(sourceArray, 0, sourceArray.Length - 1, results);
        return results;
    }

    private static void Swap<T>(ref T a, ref T b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }

    private static void Permute<T>(T[] elements, int recursionDepth, int maxDepth, ICollection<T[]> results)
    {
        if (recursionDepth == maxDepth)
        {
            results.Add(elements.ToArray());
            return;
        }

        for (var i = recursionDepth; i <= maxDepth; i++)
        {
            Swap(ref elements[recursionDepth], ref elements[i]);
            Permute(elements, recursionDepth + 1, maxDepth, results);
            Swap(ref elements[recursionDepth], ref elements[i]);
        }
    }
}

Вот функция, которая будет печатать все перестановки рекурсивно.

public void Permutations(string input, StringBuilder sb)
    {
        if (sb.Length == input.Length)
        {
            Console.WriteLine(sb.ToString());
            return;
        }

        char[] inChar = input.ToCharArray();

        for (int i = 0; i < input.Length; i++)
        {
            if (!sb.ToString().Contains(inChar[i]))
            {
                sb.Append(inChar[i]);
                Permutations(input, sb);    
                RemoveChar(sb, inChar[i]);
            }
        }
    }

private bool RemoveChar(StringBuilder input, char toRemove)
    {
        int index = input.ToString().IndexOf(toRemove);
        if (index >= 0)
        {
            input.Remove(index, 1);
            return true;
        }
        return false;
    }

class Permutation
{
    public static List<string> Permutate(string seed, List<string> lstsList)
    {
        loopCounter = 0;
        // string s="\w{0,2}";
        var lstStrs = PermuateRecursive(seed);

        Trace.WriteLine("Loop counter :" + loopCounter);
        return lstStrs;
    }

    // Recursive function to find permutation
    private static List<string> PermuateRecursive(string seed)
    {
        List<string> lstStrs = new List<string>();

        if (seed.Length > 2)
        {
            for (int i = 0; i < seed.Length; i++)
            {
                str = Swap(seed, 0, i);

                PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach(
                    s =>
                    {
                        lstStrs.Add(str[0] + s);
                        loopCounter++;
                    });
                ;
            }
        }
        else
        {
            lstStrs.Add(seed);
            lstStrs.Add(Swap(seed, 0, 1));
        }
        return lstStrs;
    }
    //Loop counter variable to count total number of loop execution in various functions
    private static int loopCounter = 0;

    //Non recursive  version of permuation function
    public static List<string> Permutate(string seed)
    {
        loopCounter = 0;
        List<string> strList = new List<string>();
        strList.Add(seed);
        for (int i = 0; i < seed.Length; i++)
        {
            int count = strList.Count;
            for (int j = i + 1; j < seed.Length; j++)
            {
                for (int k = 0; k < count; k++)
                {
                    strList.Add(Swap(strList[k], i, j));
                    loopCounter++;
                }
            }
        }
        Trace.WriteLine("Loop counter :" + loopCounter);
        return strList;
    }

    private static string Swap(string seed, int p, int p2)
    {
        Char[] chars = seed.ToCharArray();
        char temp = chars[p2];
        chars[p2] = chars[p];
        chars[p] = temp;
        return new string(chars);
    }
}

Вот ответ C #, который немного упрощен.

public static void StringPermutationsDemo()
{
    strBldr = new StringBuilder();

    string result = Permute("ABCD".ToCharArray(), 0);
    MessageBox.Show(result);
}     

static string Permute(char[] elementsList, int startIndex)
{
    if (startIndex == elementsList.Length)
    {
        foreach (char element in elementsList)
        {
            strBldr.Append(" " + element);
        }
        strBldr.AppendLine("");
    }
    else
    {
        for (int tempIndex = startIndex; tempIndex <= elementsList.Length - 1; tempIndex++)
        {
            Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);

            Permute(elementsList, (startIndex + 1));

            Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
        }
    }

    return strBldr.ToString();
}

static void Swap(ref char Char1, ref char Char2)
{
    char tempElement = Char1;
    Char1 = Char2;
    Char2 = tempElement;
}

Вывод:

1 2 3
1 3 2

2 1 3
2 3 1

3 2 1
3 1 2

Это мое решение, которое мне легко понять

class ClassicPermutationProblem
{
    ClassicPermutationProblem() { }

    private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position)
    {
         foreach (T element in list)
         {
             List<T> currentTemp = temp.ToList();
             if (!currentTemp.Contains(element))
                currentTemp.Add(element);
             else
                continue;

             if (position == list.Count)
                finalList.Add(currentTemp);
             else
                PopulatePosition(finalList, list, currentTemp, position + 1);
        }
    }

    public static List<List<int>> GetPermutations(List<int> list)
    {
        List<List<int>> results = new List<List<int>>();
        PopulatePosition(results, list, new List<int>(), 1);
        return results;
     }
}

static void Main(string[] args)
{
    List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 });
}

Вот еще одна реализация упомянутого алгоритма.

public class Program
{
    public static void Main(string[] args)
    {
        string str = "abcefgh";
        var astr = new Permutation().GenerateFor(str);
        Console.WriteLine(astr.Length);
        foreach(var a in astr)
        {
            Console.WriteLine(a);
        }
        //a.ForEach(Console.WriteLine);
    }
}

class Permutation
{
    public string[] GenerateFor(string s)
    {  

        if(s.Length == 1)
        {

            return new []{s}; 
        }

        else if(s.Length == 2)
        {

            return new []{s[1].ToString()+s[0].ToString(),s[0].ToString()+s[1].ToString()};

        }

        var comb = new List<string>();

        foreach(var c in s)
        {

            string cStr = c.ToString();

            var sToProcess = s.Replace(cStr,"");
            if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0)
            {
                var conCatStr = GenerateFor(sToProcess);



                foreach(var a in conCatStr)
                {
                    comb.Add(c.ToString()+a);
                }


            }
        }
        return comb.ToArray();

    }
}

    //Generic C# Method
            private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
            {
                var perms = new List<T[]>();

                var l = input.Length - 1;

                if (l == startIndex)
                    perms.Add(input);
                else
                {

                    for (int i = startIndex; i <= l; i++)
                    {
                        var copy = input.ToArray(); //make copy

                        var temp = copy[startIndex];

                        copy[startIndex] = copy[i];
                        copy[i] = temp;

                        perms.AddRange(GetPerms(copy, startIndex + 1));

                    }
                }

                return perms;
            }

            //usages
            char[] charArray = new char[] { 'A', 'B', 'C' };
            var charPerms = GetPerms(charArray);


            string[] stringArray = new string[] { "Orange", "Mango", "Apple" };
            var stringPerms = GetPerms(stringArray);


            int[] intArray = new int[] { 1, 2, 3 };
            var intPerms = GetPerms(intArray);

    /// <summary>
    /// Print All the Permutations.
    /// </summary>
    /// <param name="inputStr">input string</param>
    /// <param name="strLength">length of the string</param>
    /// <param name="outputStr">output string</param>
    private void PrintAllPermutations(string inputStr, int strLength,string outputStr, int NumberOfChars)
    {
        //Means you have completed a permutation.
        if (outputStr.Length == NumberOfChars)
        {
            Console.WriteLine(outputStr);                
            return;
        }

        //For loop is used to print permutations starting with every character. first print all the permutations starting with a,then b, etc.
        for(int i=0 ; i< strLength; i++)
        {
            // Recursive call : for a string abc = a + perm(bc). b+ perm(ac) etc.
            PrintAllPermutations(inputStr.Remove(i, 1), strLength - 1, outputStr + inputStr.Substring(i, 1), 4);
        }
    }