2

I just can't understand how this algorithm works. All the explanations I've seen say that if you have a set such as {A, B, C} and you want all the permutations, start with each letter distinctly, then find the permutations of the rest of the letters. So for example {A} + permutationsOf({B,C}).

But all the explanations seem to gloss over how you find the permutations of the rest. An example being this one.

Could someone try to explain this algorithm a little more clearly to me?

4

4 回答 4

1

要了解递归，您需要了解递归..

(c) 程序员的智慧

你的问题是关于这个事实，“其余的排列”是递归部分。递归总是由两部分组成：平凡案例和递归案例。琐碎案例指向没有继续递归并且应该返回某些内容的情况。

在您的示例中，微不足道的部分是{A}- 这组只有一个排列 - 本身。递归部分将是当前元素和这个“其余部分”的联合 - 即，如果您有多个元素，那么您的结果将是该元素和“其余部分”之间排列的联合。在排列方面：其余部分是当前集合，没有选定元素。即{A,B,C}在第一个递归步骤上设置，将是{A}和 "rest part": {B,C}，然后{B}是 "rest part": {A,C}- 最后{C}是 "rest part"：{A,B}

因此，您的递归将持续到“其余部分”将是单个元素的那一刻 - 然后它将结束。

于 2013-10-07T13:56:58.863 回答
0

您的问题的答案在停止标准中（在这种情况下!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);
于 2013-10-07T14:51:34.757 回答
0

这就是递归实现的重点。假设您已经有了更简单问题的解决方案，您可以递归地定义解决方案。稍加考虑，您将得出结论，您可以对更简单的情况进行相同的考虑，使其更加简单。继续下去，直到你遇到一个简单到可以解决的案例。这种足够简单的情况称为递归的底部。

另请注意，您必须遍历所有字母，而不仅仅是A第一个元素。因此，您得到所有​​排列：

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

花一点时间，试着写下一组四个字母的所有排列{A, B, C, D}。你会发现你使用的算法和上面的递归很接近。

于 2013-10-07T13:53:16.230 回答
0

那么，让我们分析一下这个例子{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
于 2013-10-07T14:31:40.137 回答