递归实现全排列

1 求解思路

??全排列表示把集合中元素的所有按照一定的顺序排列起来，使用P(n, n) = n!表示n个元素全排列的个数。P(n, n)中的第一个n表示元素的个数，第二个n表示取多少个元素进行排列。

??给定一个n个元素数组，其全排列的过程可以描述如下：

• 任意取一个元素放在第一个位置，则有n种选择；
• 再剩下的n-1个元素中再取一个元素放在第二个位置则有n-1种选择，此时可以看做对n-1个元素进行全排列；
• 重复第二步，直到对最后一个元素进行全排列，即最后一个元素放在最后一个位置，全排列结束。

??以数组{1,2,3}为例，其全排列的过程如下：

• 1后面跟（2,3）的全排列；
• 2后面跟（1,3）的全排列；
• 3后面跟（1,2）的全排列。

??图示如下：

2 考虑数组中有重复元素的问题

??如果数组中有重复的元素，变成了{1,2,2}，那么它的全排列就不能完全按照上面的方法求解，需要做稍微的改动。

??因为全排列是将不同元素依次换到当前位置后，再对后面的元素求全排列。如果将重复的元素多次换到当前位置的话，那么就会出现相同的排列。为了避免，我们禁止将相同的元素多次换到当前位置即可。

??例如，对{1，2，2}，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。

??这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换(第二次出现就不再交换，比如{1,2,2,2,2,2}，与第一个2交换，不再与后面的2交换)。

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include "TreeNode.h"
#include "ListNode.h"
using namespace std;

// 全排列个数
int sum=0;

// 打印数组内容
void print(int array[],int len){
    printf("{");
    for(int i=0; i<len;++i)
        cout<<array[i]<<" ";
    printf("}\n");
}

bool isSwap(int arr[], int len, int index){
    for(int i = index + 1; i < len; i++){
        if(arr[i] == arr[index])
            return false;
    }
    return true;
}

// 实现两数交换
void mySwap(int* o,int i,int j){
    int tmp = o[i];
    o[i] = o[j];
    o[j] = tmp;
}

// 递归实现数组全排列并打印，妙啊！
void permutation(int array[],int len,int index){
    // 全排列结束
    if(index == len){
        ++sum;
        print(array, len);
        cout<<"************************"<<endl;
    }
    else{
        for(int i=index;i<len;++i){
            // 首先判断是否可以交换
            if(isSwap(array, len, i)){
                // 任意取一个元素放在该位置！！！！！！
                // 将第i个元素交换至当前index下标处
                mySwap(array, index, i);
                // 以递归的方式对剩下元素进行全排列
                permutation(array, len, index + 1);
                // 将第i个元素交换回原处，以供下一个元素与第一个元素交换
                mySwap(array, index, i);
            }
        }
    }
}

int main(int argc, char* argv[]){

    int array[3]={1,2,3};
    permutation(array, 3, 0);
    cout<<"sum:"<<sum<<endl;

    return 0;
}

递归实现全排列

原文：https://www.cnblogs.com/flyingrun/p/13445597.html