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

Вот чисто функциональная реализация 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 переполнение.

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

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

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

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

Обратите внимание, что набор размера n имеет 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

Построение на решении @Peter, вот версия, которая объявляет простой LINQ-стиль Permutations() дополнительный метод, который работает над любым 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]);
        }
    }
}

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 (строка, 0);