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

Question

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

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

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

Answer 1

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

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

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

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

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

* +1019 *

Пример: * ** +1023 тысяча двадцать-два * Если в наборе только один элемент ->
верни его.
Пермь (а) -> а Если в наборе есть два символа: для каждый элемент в нем: вернуть элемент, с перестановкой Остальные элементы добавлены, вот так:
Пермь (ab) ->
a + perm (b) -> ab
b + perm (a) -> ba
Далее: для каждого символа в наборе: вернуть символ, объединенный с разрешением> остальной части набора Пермь (abc) ->
a + perm (bc) -> abc , acb
b + perm (ac) -> bac , bca
c + perm (ab) -> cab , cba
Пермь (abc ... z) ->
a + perm (...), b + perm (....)
....

Я нашел псевдокод на 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;

        a ^= b;
        b ^= a;
        a ^= b;
    }

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

Answer 2

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

EDIT

Вот моя общая функция, которая может возвращать все перестановки (не комбинации) из списка 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 или выше.

Answer 3

Здесь я нашел решение. Он был написан на 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;
}

Answer 4

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

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

Answer 5

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

Answer 6

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

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

Answer 7

Слегка измененная версия в 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;
    }
}

Answer 8

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

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

Использование Except приведет к удалению всех вхождений, т. Е. Когда 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 или удалите дубликаты после возврата любым удобным вам способом.

Answer 9

Вот простое решение в 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)));
        }
    }
}

Answer 10

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

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