c++ - 递归生成排列

Question

我发现递归很难理解，除了像阶乘这样非常直接的递归。如果我想打印一个字符串的所有排列，假设字符串长度为 5，比如 "abcde"，长度为 7 的排列应该是

abced
abdce
abdec
abecd
abedc
acbde
acbed
acdbe
acdeb
acebd
acedb
adbce
adbec
adcbe
adceb
adebc
adecb
aebcd
aebdc
aecbd
aecdb
aedbc
aedcb
bacde
baced
badce
badec
baecd
baedc
bcade
bcaed
...

如果我想要一个递归来计算 5 的阶乘的所有排列，例如 4、3、2 或 1。我应该使用哪种算法？ C++ 库中是否有用于此的任何函数？

假设打印输出应该是这样的:

acbd
bcad
abc
bac
ab
ba

Answer 1

使用递归算法，很像mathematical induction .首先需要处理基本情况，然后找到子问题模式。

对于阶乘，将问题定义为 n 的 F(n) 阶乘。

1. 基本情况，F(0)=1
2. 子问题模式，F(n)=n!=n*(n-1)!=n*F(n-1)

对于排列，将 P(E) 定义为集合 E 的所有排列。

1. 基本情况，P({}) = {{}}
2. 子问题模式。考虑排列的过程，假设我选择了第一个元素 x，然后我们得到了一个子问题，P(E-x)，然后对于每个 p在 P(E-x) 中，x 到前面，我们得到了所有以元素 x 开头的排列，迭代 x 你得到了所有排列，又名 P(E)。

在 C++ 中，您可以使用 next_permutation .

上述想法的示例代码如下:

// generate permutation of {a[st], a[st+1], ..., a[ed]}
void P(char a[], int st, int ed) {
    if (st > ed) { puts(a); return; } // nothing to generate
    for (int i=st; i<=ed; ++i) {
        swap(a[st], a[i]);            // enumerate first element
        P(a, st+1, ed);
        swap(a[st], a[i]);            // recover
    }
}

在 http://ideone.com/zbawY2 上查看.