C++全排列算法

参考：【基础算法】- 全排列

代码参考上面链接，花了一些功夫才读懂，添加了注释。

经验是：读代码时拿纸笔模拟单步执行，方便理解。

还学到了不申请额外空间完成值交换的骚操作。感谢作者。

#include <iostream>
using namespace std;

//交换数值的骚操作，三个异或。
void swap(char* array , int i , int j){
    //位操作输入有4种情况，异或操作^的输出0、1数量是2：2，能保持足够的信息量。&、|的结果则是1：3，3：1。
    //C没有同或。
    if(i != j){
        array[i]^=array[j];array[j]^=array[i];array[i]^=array[j];
    }
}

void allsort(char* array , int start , int end){
    
    if(start < end-1){//当元素数>=1时
        for(int i = start ; i < end; i++){
            //把第一个元素分别和后面的元素交换，相当于轮流将a,b,c放到第一的位置
            swap(array , i , start);
            //确定了新的第一元素后，递归排列后面的
            allsort(array , start+1 , end);
            //再交换回来，恢复原顺序。否则元素位置错乱，以后无法保证每个元素都被换到第一的位置
            swap(array , i , start);
        }
    }else{//当只剩1个元素时
        for(int i = 0 ; i < end ; i++) {
            cout << array[i];
        }
        cout << endl;
    }
}

int main(int argc, const char * argv[]) {
    char array[] = {'a','b', 'c','d'};
    allsort(array,0,4);
    return 0;
}

输出结果如下：

abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc