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

Question

我在有竞争力的程序员手册做同样的事情，但我正在努力理解它背后的逻辑。
它指出：

Like subsets, permutations can be generated using recursion. The following function search goes through the permutations of the set {0,1,...,n¡1}. The function builds a vector permutation that contains the permutation, and the search begins when the function is called without parameters.

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

Each function call adds a new element to permutation. The array chosen indicates which elements are already included in the permutation. If the size of permutation equals the size of the set, a permutation has been generated.

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

Answer 1

您可以这样拆分代码：

void search() {
    if (permutation.size() == n) {
        // we have a valid permutation here
        // process permutation
    } else {

        // The permutation is 'under construction'.
        // The first k elements are fixed,
        // n - k are still missing.
        // So we must choose the next number:
        for (int i = 0; i < n; i++) {

            // some of them are already chosen earlier
            if (chosen[i]) continue;

            // if i is still free:

            // signal to nested calls that i is occupied
            chosen[i] = true;
            // add it to the permutation
            permutation.push_back(i);

            // At the start of this nested call,
            // the permutation will have the first (k + 1)
            // numbers fixed.
            search();

            // Now we UNDO what we did before the recursive call
            // and the permutation state becomes the same as when
            // we entered this call.
            // This allows us to proceed to the next iteration
            // of the for loop.

            chosen[i] = false;
            permutation.pop_back();
        }
    }
}

直觉可能是 search() 是“以各种可能的方式完成当前部分构造的排列并处理所有排列”。

如果已经完成，我们只需要处理一个可能的排列。如果不是，我们可以先以各种可能的方式选择第一个数字，然后对每个数字递归完成排列。

Answer 2

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

首先你什么都没有。取 1 ，然后是 2 ，然后是 3 。你现在无处可去，即 Dead End 。你打印你当前的排列是 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();
        }
    }
}

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

Can someone explain me this code which generates all the possible permuations of a given set?

c++

algorithm

recursion

permutation

set