再帰生成全配列【C/C++】

簡単に述べる
シーケンスの全配列を生成
アルゴリズム擬似コード
入力:

n:シーケンス長

を表す

char*a:対応するシーケンス

出力:

このシーケンスの全配列

要件を満たす:

は全配列

を使用する必要がある.

対応コードのパラメータvoid pomi(char *arr, int k);

は、pomi関数の内部の内容

のみを修正する.
アルゴリズムの考え方:
kが0の場合、このシーケンスを出力します.そうでなければ、前のn-k文字を完全に同じにした後、新しいシーケンスを作成します.n-k番目のビットを選択し、後ろの保持順序を後ろに置きます.再帰に入る

#include 
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);
    }
}