递归生成全排列【C/C++】

简述

生成一个序列的全排列

算法伪代码

输入：

• n：表示序列长度
• char* a: 对应的序列

输出：

• 这个序列的全排列

满足要求：

• 必须使用全排列
• 对应的代码的参数 void pomi(char *arr, int k);
• 只能修改pomi函数内部的内容

算法思路：

k为0的时候，输出这个序列。
否则，创建一个新序列，在保持前n-k个字符都完全一样之后。选一个到第n-k位，并将后面的保持顺序放到之后。
进入到递归

#include <iostream>
using namespace std;
int n;
char *a;
void pomi(char *arr, int k);
int main(){
    cin >> n;
    a = new char[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    pomi(a, n);
}

void pomi(char *arr, int k) {
    if(k==0) {
        for (int i = 0; i < n; ++i) cout << arr[i];
        cout << endl; return;
    }
    char *arr_ = new char[n];
    int i, j;
    // copy from old char* 
    for (j = 0; j < n-k; ++j) arr_[j] = arr[j];
    // n-k mean n-k length char-site you have already choosen.
    for (i = n-k; i < n; ++i) {
        arr_[n-k] = arr[i];
        for (j=n-k+1; j <= i; ++j) arr_[j] = arr[j-1];
        for (j=i+1; j < n; ++j) arr_[j] = arr[j];
        pomi(arr_, k-1);
    }
}