n个互异字符串的全排列

        本节讨论通过递归调用实现互异字符串的全排列。

        考虑两个字符的全排列为两者交换顺序；三个字符的全排列则可以用抽取一个交换到第一个位置，剩下的两个字符仿照两个字符的情况实现全排列；以此类推，当n个字符全排列，先抽取一个 交换到第一个位置，剩下的n-1个字符实现全排列，此时则是递归调用的形式。

        下面为p位置到q位置的全排列示意图：

        

 先编写交换函数swap()

// 交换位置
void swap(char a[], int p, int q) {
    char temp = a[p];
    a[p] = a[q];
    a[q] = temp;
}

 由于过程中需要打印出字符数组的元素，故需要编写打印函数printArray()

// 打印数组
void printArray(char a[],int n){
    for(int i=0; i<n; i++) 
        cout<<a[i];
}

整合以上可编写全排列函数perm()

// 全排列
void perm(char a[],int p,int q) {
    if (p == q) {
        printArray(a,q+1);
        cout<<endl;
    }else {
        int i;
        for(i=p; i<=q; i++) {
            swap(a,p,i);
            perm(a,p+1,q);
            swap(a,p,i);
        }
    }
}

注意到要求字符串互异，为增强程序的鲁棒性，可编写判定互异的函数difference()

// 判断互异
bool diffenerce(char a[],int n){
     for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            if(a[i]==a[j]){
                cout<<"请重新输入不同的字符:"<<endl;
                return false;
            }
        }
    }
    return true;
}

mian.cpp

int main() {
    cout<< "请输入字符数n:" <<endl;
    int n;
    cin>>n;
    cout<< "请输入n个不同的字符:" <<endl;
    char *a = (char*)malloc(sizeof(char)*n);
    bool flag;
    do{
        for(int i=0; i<n; i++) {
            cin>>a[i];
        }
        flag = diffenerce(a,n);
    }while(!flag);
    cout<< "以上n个不同字符的全排列为:" <<endl;
    perm(a,0,n-1);
    free(a);
    return 0;
}

全部程序如下：

#include <iostream>

using namespace std;

// 交换位置
void swap(char a[], int p, int q) {
    char temp = a[p];
    a[p] = a[q];
    a[q] = temp;
}

// 打印数组
void printArray(char a[],int n){
    for(int i=0; i<n; i++) 
        cout<<a[i];
}
// 全排列
void perm(char a[],int p,int q) {
    if (p == q) {
        printArray(a,q+1);
        cout<<endl;
    }else {
        int i;
        for(i=p; i<=q; i++) {
            swap(a,p,i);
            perm(a,p+1,q);
            swap(a,p,i);
        }
    }
}
// 判断互异
bool diffenerce(char a[],int n){
     for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            if(a[i]==a[j]){
                cout<<"请重新输入不同的字符:"<<endl;
                return false;
            }
        }
    }
    return true;
}

int main() {
    cout<< "请输入字符数n:" <<endl;
    int n;
    cin>>n;
    cout<< "请输入n个不同的字符:" <<endl;
    char *a = (char*)malloc(sizeof(char)*n);    //为字符数组分配内存空间
    bool flag;
    do{
        for(int i=0; i<n; i++) {
            cin>>a[i];
        }
        flag = diffenerce(a,n);
    }while(!flag);
    cout<< "以上n个不同字符的全排列为:" <<endl;
    perm(a,0,n-1);
    free(a);    //释放空间
    return 0;
}