面试算法题-全排列C++实现（递归&去重复）

问题描述

全排列：给定元素序列，如{1，2，3}，他们所有可能的排列组合有{1，2，3}、{1，3，2}、{2，1，3}、{2，3，1}、{3，1，2}、{3，2，1}

思路

关于递归：

假设给定元素序列是{1，2，3，4}，则在改变第一个元素的情况下，我们共有四种选择，{1，2，3，4}、{2，1，3，4}、{3，2，1，4}、{4，2，3，1}，而这四种选择分别对应着原始序列的第一个元素与后面的元素进行交换。注意到此时我们已经取遍了第一个元素不同的所有情况。确定第一个元素之后，剩下的元素序列中元素个数为3，同样，我们可以确定3种不同的情况... 直到剩下的元素序列元素个数为1，有且只有一种情况，我们到达递归的终点。

关于重复：

当交换操作之后得到的序列与交换之前的序列相等时，我们将会得到重复的子序列。例如，给定元素序列{1，2，2}，第二、三次交换得到的序列都是{2，1，2}，此时我们会将第一个元素为2的所有情况打印两遍。为了解决重复，我们可以在交换前进行判断，如果此时需要交换的元素(如第二次我们需要交换1和2，需要交换的元素是2，第三次需要交换的元素也是2)在这一轮交换的队列里出现过，我们就跳过这个元素。
具体的代码实现如下。

代码

#include <iostream>

using namespace std;

// 交换元素
void my_swap(char *list, int i, int j)
{
    char temp = 0;
    temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

void permutation(char *list, int N, int head)
{
    int tell = 0;
    // 是否到达递归终点
    if(head >= N){
        for(int j = 0; j < N; j++){
            cout<<list[j];
        }
        cout<<endl;
        return;
    }
    // 遍历元素序列中的所有元素
    for(int i = head; i < N; i++){
        tell = 0;
        // 与之前交换过的元素进行比较，若之前有相同的元素被交换过，则tell置为1
        for(int k = i; k >=head; k--){
            if(i != k && list[i] == list[k]){
                tell = 1;
            }
        }
        // 如果tell非1，则进行交换并递归
        if(!tell){
            my_swap(list, i, head);
            permutation(list, N, head+1);
            my_swap(list, i, head);
        }

    }
}

int main()
{
    int N;
    cin>>N;

    char *list = new char[N];

    for(int i = 0; i < N; i++){
        cin>>list[i];
    }
    permutation(list, N, 0);
    delete[] list;
    
    system("pause");
    return 0;
}

面试算法题-全排列C++实现（递归&去重复）

原文：https://www.cnblogs.com/lullaby233/p/14660742.html