全排列

求全排列最简单的就是递归了
123 的全排列共有 6 个， 123 的全排列等于以 1 开头 23 的全排列， 加上以 2 开头 13 的全排列，加上以 3 开头 21 的全排列。

一个数列的全排列就是每一个数分别与第一个数交换（每一个数字都做一回头）后所得数列全排列的和。去掉第一个数字，后面数列的全排列怎么求？？？显然一样的求法，递归就行。

什么时候结束递归呢？？？显然当只剩下一个数字的时候就求得了一个全排列。

permutation.jpg

#include <cstdio>

void swap(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void permutation(int a[], int begin, int end) {
    if (begin == end - 1) {
        for(int i=0; i<end; i++) {
            printf("%d",a[i]);
        }
        printf("\n");
        return;
    }

    // 后面的数依次与第一个数交换
    for(int i=begin; i<=end-1; i++) {
        swap(a, begin, i); // 包括自己和自己交换
        permutation(a, begin+1, end);  // 递归处理第一个数后面数列的排列
        swap(a, begin, i); // 得到一个排列后再把原来交换的数换回来，开始下一个排列的计算
    }
}

int main() {
    int a[3] = {1,2,3};

    permutation(a,0,3);

    return 0;
}

关于去重，例如 122，上面的算法仍然会输出 6 个数列，怎么去除重复的排列呢？？？ 网上说的是假如要交换的两个数字下标是 i, j (i 是头) 只有当 [i,j) 之间没有和 a[j] 相同的数字才交换。我也不大理解，水平太菜, 这个递归排列我都理解了好长时间？？？？

bool canSwap(int a[], int i,int j) {
    // 只有当 [i,j) 之间没有和 a[j] 相同的数字才交换
    for(int x=i; x<j; x++) {
        if(a[x]==a[j]) {
            return false;
        }
    }

    return true;
}

// 后面的数依次与第一个数交换
for(int i=begin; i<=end-1; i++) {
    if(canSwap(a,begin,i)) {
        swap(a, begin, i); // 包括自己和自己交换
        permutation(a, begin+1, end); // 递归处理第一个数后面数列的排列
        swap(a, begin, i); // 得到一个排列后再把原来交换的数换回来，开始下一个排列的计算
    }
}