数据结构与算法——Permutation a String

state space tree

state space tree

Back Tracking (DFS)

brute force

recursion

Branch and Bound (BFS)

算法一：

#include <iostream>
using namespace std;
void permutation(char S[], int k){
    static int A[10] = {0};
    static char res[10] = {0};
    if(S[k] == '\0'){
        res[k] = '\0';
        printf("%s\n", res);
    }
    else{
        for(int i = 0; S[i] != '\0'; ++i){
            if(A[i] == 0){
                A[i] = 1;
                res[k] = S[i];
                permutation(S, k+1);
                A[i] = 0;
            }
        }
    }
}
int main()
{
    char S[] = "ABC";
    permutation(S, 0);

    return 0;
}

output:

ABC
ACB
BAC
BCA
CAB
CBA

算法二：

#include <iostream>
using namespace std;
void perm(char S[], int l, int h){
    if(l == h){
        printf("%s\n", S);
    }
    else{
        for(int i = l; i <= h; ++i){
            swap(S[l], S[i]);
            perm(S, l+1, h);
            swap(S[l], S[i]);
        }
    }
}
int main()
{
    char S[] = "ABC";
    perm(S, 0, 2);
    return 0;
}

output:

ABC
ACB
BAC
BCA
CBA
CAB