有人可以向我解释这段生成给定集合的所有可能排列的代码吗？

Question

我在竞争性程序员手册中找到了一个递归代码来执行相同的操作，但我很难理解其背后的逻辑。
\n它指出：

\n

\n

与子集一样，排列可以使用递归生成。下面的函数搜索遍历集合 {0,1,...,n\xc2\xa11} 的排列。该函数\n构建一个包含该排列的向量排列，并且在不带参数调用该函数时\n开始搜索。\n

\n

\n

void search() {\n    if (permutation.size() == n) {\n        // process permutation\n    } else {\n        for (int i = 0; i < n; i++) {\n            if (chosen[i]) continue;\n            chosen[i] = true;\n            permutation.push_back(i);\n            search();\n            chosen[i] = false;\n            permutation.pop_back();\n        }\n    }\n}\n

\n

\n

每个函数调用都会向排列添加一个新元素。所选数组\表示哪些元素已包含在排列中。如果\n排列的大小等于集合的大小，则已生成排列。\n

\n

\n

我似乎无法理解正确的直觉和所使用的概念。
\n有人可以解释一下这段代码在做什么以及它背后的逻辑是什么吗？

\n

Answer 1

我会尽力给你一些直觉。主要思想是回溯。您基本上会构建一个解决方案，直到您面临死胡同。当你确实面临死胡同时，回到最后的位置，在那里你可以做一些与上次不同的事情。让我来看看我为 绘制的这个模拟n = 3。

首先你什么都没有。采取1，然后2然后3。你现在无处可去，即死胡同。您打印当前的排列，即123您现在做什么？回去吧，1因为你知道你可以利用3这段时间开辟另一条路。那么这次你以同样的方式得到什么呢？132。你能用 1 做更多的事情吗？ 没有。现在回到一无所有并重新开始同样的事情，现在获取2。现在你明白了，对吧？

对于代码中发生的同样的事情：

void search() {
    if (permutation.size() == n) /// DEAD END
    { 
        // process permutation
    } 
    else {
        for (int i = 0; i < n; i++) {

            if (chosen[i]) continue; /// you have already taken this in your current path , so ignore it now

            chosen[i] = true; /// take it , as you haven't already
            permutation.push_back(i);

            search(); // go to the next step after taking this item

            chosen[i] = false; // you have done all you could do with this , now get rid of it
            permutation.pop_back();
        }
    }
}