全排列怎么做？

大家好，我是陆砚码。今天我们来聊聊全排列这个问题。全排列是信息学奥赛中常见的题型，主要考察递归和深搜算法。接下来，我会用通俗易懂的方式，带你一步步理解全排列的解法。

解法1：递归

递归是一种自上而下的解决问题的方法。对于全排列，我们可以这样思考：已知原字符串下标从0开始，长度为len。我们要找出从k到len-1这一子串的全排列。具体步骤如下：

• 如果k等于len-1，说明我们到了最后一个字符，此时输出整个字符串，即为一种排列。
• 否则，遍历子串中每个字符，将其与下标k的字符交换，然后递归求出下标k+1到len-1这一子串的全排列。
• 每次递归结束后，都要将字符串还原到调用函数时的状态。

这种方法类似于冒泡排序中的冒泡过程，每次交换后，下标k到len-1的字符仍然是升序的。

解法2：深搜

深搜是一种自下而上的解决问题的方法。我们可以使用一个字符数组a来保存要输出的排列结果，以及一个布尔数组vis来记录每个字符是否已经使用过。具体步骤如下：

• 遍历字符串，如果找到一个未使用的字符，就将其放在第k位置，然后递归确定第k+1位置的字符。
• 如果已经确定完第len-1字符，那么此时输出数组a。
• 注意状态还原，每次递归结束后都要将vis数组恢复到初始状态。

这两种方法都是解决全排列问题的有效方法。下面是相应的代码实现：

// 递归方法
#include
#include 
using namespace std;
char s[10];
int len;
void arrange(int k) {
    if(k == len-1) {
        cout << s << endl;
        return;
    }
    for(int i = k; i < len; ++i) {
        swap(s[k], s[i]);
        arrange(k+1);
    }
    for(int i = k; i < len-1; ++i)
        swap(s[i], s[i+1]);
}
int main() {
    cin >> s;
    len = strlen(s);
    arrange(0);
    return 0;
}

// 深搜方法
#include
#include 
using namespace std;
char s[10], a[10];
int len;
bool vis[10];
void dfs(int k) {
    if(k == len) {
        cout << a << endl;
        return;
    }
    for(int i = 0; i < len; ++i) {
        if(vis[i] == false) {
            vis[i] = true;
            a[k] = s[i];
            dfs(k+1);
            vis[i] = false;
        }
    }
}
int main() {
    cin >> s;
    len = strlen(s);
    dfs(0);
    return 0;
}

以上就是全排列的两种解法，希望对大家有所帮助。如果你对编程还有其他疑问，欢迎来「思享编程网」（www.sxgpb.com）和我交流。