重复数字全排列的全新去重思想（非循环）C语言

前言

本文介绍一种求有重复数字的全排列的去重思想，该算法思想在时间上优于目前使用最广泛的循环去重思想。

题目展示

参考题目：Acwing—递归实现排列型枚举II

参考题目：Leetcode—全排列II

因力扣的提交格式复杂，在这里用Acwing的题目做演示。

函数栈帧

若想了解该种思想，就要先知道什么是函数栈帧。

顾名思义，函数与栈和帧的结合，每调用一个函数就会在栈区上开辟一块空间，就像视频的每一帧一样，当函数调用结束后，这一帧也会随之销毁，在栈区开辟的空间也会还给操作系统。

如果我们在函数内部创建一个数组的话，每调用一次函数，就会创建一次这个数组，该数组只会保存在当前帧里，当函数调用结束，空间没了，这个数组自然也就没了。

f(int time)
{
	int st[10];
	f(time + 1);
}
int main()
{
	fun(1);
	return 0;
}

如果你运行上面的代码，就会出现下面这样的情况：

由于函数的每一帧都在栈区内保存，所以后面的帧销毁之前，前面的帧内创建的st数组会一直保存，本文要介绍的思想就利用了函数栈帧的该种性质。

去重思想

这里先展示代码，随后进行详细解读。

全局变量与主函数 （与正常全排列无区别）

int N = 0;
int data[10];
int arr[10];
int used[10];
//...
int main()
{
	scanf("%d", &N);
	int i = 0;
	for (i = 0; i < N; i++)
	{
		scanf("%d", &data[i]);
	}
	dfs(0);//递归用的函数
	return 0;
}

其中，N是数据的个数，data是保存数据的数组，arr是递归时保存每一帧状态的，used是记录某个数字是否被用过，这些变量与正常的全排列代码中的意义相同。

函数

为了观看方便，将用图片展示，与正常全排列代码不同之处已用红色标出。

在本题中，step代表当前要排列的位置的下标，若想去重，就要保证每个数在每个位置上只出现一次，同时还不能影响其他分支。

因此，我们在函数内部创建数组st，用来保存当前位置下有哪些数被用过了，被用过了就跳过这个数即可。

拿数据data10={1，1，3} 举例，第一个位置首先赋值为data0，同时让st[data0]+=1，表示在第一个位置data0 已经用过了，当第一个位置为data0 的分支全部结束后，就会把第一个位置赋为data1，但此时data0 和data1 相同，即st[data1] 和st[data0] 相同，都等于1，这样就把这第二个1给跳过了。

当我们进入到下一个位置时，又会创建一个新的st数组来保存当前位置的使用记录，这样前面的st数组既不会影响到后面的，也不会被后面的st数组覆盖，就能达到去重的效果。

错误示范

博主一开始并没有想到用函数栈帧的性质，而是创建一个10X10的全局数组，让每一行代表每个step（每个位置），每一列代表每个数，哪个位置的哪个数被用了，就让其自增1。

这样不就相当于有了十个一维数组，每个一位数组都代表每个位置的数，不也可以达成上文讲述的效果吗？

但是这样却忘记了一件事，数组的记录不能影响其他的分支，拿{1，1，3}举例。

下面将展示两张图，其中step代表位置，从上到下代表选择，每一个紫色框代表一帧

以上两张图便是一正确、一错误的两种方法最直观地解释了。

思想优劣

若是题目没有要求按照字典序输出，则这种思想与循环思想相比，最大的优势是不需要排序，节约了排序消耗的时间，降低了代码的复杂程度。

一般这种全排列题目，给定的N不会太大，所以排序的时间其实也很短，主要是降低了代码的复杂程度。

其次，即使题目要求按照字典序输出，该思想在时间上依然优于循环思想，Acwing上两种代码各提交十次去掉极值后取平均值，比循环思想快约20ms，几乎可以忽略不计。

由此得出：

• 题目不要求字典序——优先选用本文介绍的思想
• 题目要求字典序——两者皆可，差别不大

AC代码

下面展示Acwing的通过代码

#include<stdio.h>
#include<stdlib.h>
int n=0;
int arr[10];
int data[10];
int used[10];
f(int step)
{
    int st[10]={0};
    if(step==n)
    {
        int i=0;
        for(i=0;i<n;i++)
        {
            printf("%d ",arr[i]);
        }
        printf("\n");
        return;
    }
    int i=0;
    for(i=0;i<n;i++)
    {
        if(used[i]==0&&st[data[i]]==0)
        {
            used[i]=1;
            st[data[i]]=1;
            arr[step]=data[i];
            f(step+1);
            used[i]=0;
        }
    }
}
int cmp(const void* a,const void* b)
{
    int* _a=(int*)a;
    int* _b=(int*)b;
    return *(_a)-*(_b);
}
int main ()
{
    scanf("%d",&n);
    int i=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&data[i]);
    }
    qsort(data,n,4,cmp);
    f(0);
    return 0;
}

感谢您的阅读与耐心~ 如有错误烦请指出~ 谢谢~