Как работает алгоритм рекурсивной печати перестановок массива?

Question

Я просто не понимаю, как работает этот алгоритм. Все объяснения, которые я видел, говорят, что если у вас есть набор, такой как {A, B, C}, и вы хотите все перестановки, начните с каждой буквы отчетливо, а затем найдите перестановки остальных букв. Так, например, {A} + перестановки Of ({B, C}).

Но все объяснения, похоже, блестят, как вы найти перестановки отдыха. Примером является this one.

Может ли кто-нибудь попытаться объяснить этот алгоритм немного более четко для меня?

Answer 1

В этом весь смысл Рекурсивный реализация. Вы рекурсивно определяете решение, предполагая, что у вас уже есть решение для более простой проблемы. С небольшим усилием вы придете к выводу, что вы можете сделать то же самое для более простого случая, делая его еще более простым. Продолжайте, пока не достигнете случая, достаточно простого для решения. Этот достаточно простой случай известен как внизу для рекурсии.

Также обратите внимание, что вам нужно перебирать все буквы, а не только A, являясь первым элементом. Таким образом, вы получаете все перестановки, как:

{{A} + permutationsOf({B,C})} +{{B} + permutationsOf({A,C})} + {{C} + permutationsOf({A,B})}

Уделите минуту и ​​попытаться записать все перестановки множества из четырех букв говорят {A, B, C, D}. Вы обнаружите, что алгоритм, который вы используете, близок к рекурсии выше.

Answer 2

Чтобы понять рекурсию, что вам нужно понять рекурсию ..

(с) мудрость программиста

Ваш вопрос о том факте, что «перестановками остальных» является то, что рекурсивной части. Рекурсия всегда состоит из двух частей: тривиального случая и случая рекурсии. Тривиальный случай указывает на случай, когда нет продолжения рекурсии, и что-то должно быть возвращено.

В вашем примере тривиальная часть будет {A} - есть только одна перестановка этого набора - сама. Рекурсивная часть будет объединением текущего элемента и этой «части отдыха» - то есть, если у вас есть несколько элементов, тогда ваш результат будет объединением перестановки между этим элементом и «частью отдыха». В терминах перестановка: остальная часть тока установлена ​​без выбранного элемента. То есть для набора {A,B,C} на первый шаге рекурсии, которая будет {A} и «остальная часть»: {B,C}, затем {B} и «остальная часть»: {A,C} - и, наконец, {C} с «остальной частью»: {A,B}

Так что ваша рекурсия будет длиться до момента, когда «остальная часть» будет единым элементом, а затем она закончится.

Answer 3

Итак, давайте проанализируем пример {A, B, C}.

Во-первых, вы хотите извлечь из него один элемент и получить остальное.Таким образом, вы должны были бы написать какую-то функцию, которая будет возвращать список пар:

pairs = [ (A, {B, C}) 
      (B, {A, C}) 
      (C, {A, B}) ] 

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

for pair in pairs do 
    head <- pair.fst // e.g. for the first pair it will be A 
    tails <- perms(pair.snd) // e.g. tails will be a list of permutations computed from {B, C} 

Вам необходимо прикрепить head к каждому хвосту от tails, чтобы получить полную перестановку. Таким образом, полный цикл будет:

permutations <- [] 
for pair in pairs do 
    head <- pair.fst // e.g. for the first pair it will be A 
    tails <- perms(pair.snd) // e.g. tails will be a list of permutations computed from {B, C} 

    for tail in tails do 
     permutations.add(head :: tail); // here we create a complete permutation 

head :: tail означает, что мы придаем один элемент head к началу списка tail.

Ну, как реализовать perms Функция, используемая во фрагменте tails <- perm(pair.snd). Мы просто сделали! Вот что такое рекурсия. :)

Нам еще нужен базовый случай, так:

perms({X}) = [ {X} ] // return a list of one possible permutation 

и функция для всех остальных случаев выглядит следующим образом:

perms({X...}) = 
    permutations <- [] 
    pairs <- createPairs({X...}) 
    for pair in pairs do 
    head <- pair.fst // e.g. for the first pair it will be A 
    tails <- perms(pair.snd) // e.g. tails will be a list of permutations computed from {B, C} 

    for tail in tails do 
     permutations.add(head :: tail); // here we create a complete permutation 

return permutations 

Answer 4

Ответ на ваш вопрос находится в halting- критерия (в данном случае !inputString.length).

http://jsfiddle.net/mzPpa/

function permutate(inputString, outputString) { 
    if (!inputString.length) console.log(outputString); 
    else for (var i = 0; i < inputString.length; ++i) { 
     permutate(inputString.substring(0, i) + 
        inputString.substring(i + 1), 
        outputString + inputString[i]); 
    } 
} 

var inputString = "abcd"; 
var outputString = ""; 
permutate(inputString, outputString);