c++三种写法写全排列

题目描述

（1537. 递归实现排列类型枚举 II）

这几天写算法课设有一个题本质问的就是重复数字全排列，比这个多加了一些判断。起初搜题解大部分都是通过递归求解，在此我还写了两种非递归的求解方案，可能会有一些啰嗦，欢迎大佬指正

算法1

(非递归版dfs)

可以直接看代码注释

#include <iostream>
#include <string>

using namespace std;

int d[20]; //d数组用来存放每个数字含有几个
int n;
int f[20]; //表示栈的第n位应该从数字几开始遍历
int st = -1;
int num[20];

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++) 
	{
	    cin >> num[i];
	    d[num[i]] ++;
	}
	int nm[20];//模拟栈
	int st = 0;
	while(st > -1)
	{
	    if(st == n) 
	    {
	        for(int i = 0; i < n; i ++) cout << nm[i] << " ";
	        cout << endl;
	        st--; //栈指针前移一位， 表示弹出末尾的字符
			if (st < 0) break; // 全部弹出就要退出
			d[nm[st]] ++; //由于弹出了最后一位的数字，所以要把最后一位数字的数量再往上+1
			nm[st] = 0;
			continue;
	    }
	    if (f[st] == 9) // 对某一位从9开始进行特殊判断， 9在这一位上已经用过了，所以还要进1， 但是进1 就是两位数，
	                    //所以证明这一位已经没有可选条件了，必须对上一位进行弹出
		{
			st--;
			if (st < 0) break;
			d[nm[st]] ++;
			nm[st] = 0;
			for (int i = st + 1; i <= n; i++)  f[i] = -1;
		}
		for (int i = f[st] + 1; i < 10; i++)  //普通条件，对这一位遍历可以入栈的值
		{
			if (st < 0) break;
			if (d[i] > 0)
			{
				f[st] = i;
				d[i] --;
				nm[st] = i;
				st++;
				break;
			}
			else if (i == 9 && d[i] < 1) //一直到最后都没有值可以入栈， 对上一位再进行弹出
			{
				st--;
				if (st < 0) break;
				d[nm[st]] ++;
				nm[st] = 0;
				for(int i = st + 1; i <= n; i++)  f[i] = -1;
			}
		}
	}
	return 0;
}

算法2

(普通的递归dfs)

就是最普通的dfs

#include <bits/stdc++.h>

using namespace std;

int num[20], nm[20];
int d[20], k;
int n, m, idx;

void dfs(int x) 
{
    if(x == n)
    {
        for(int i = 0; i < n; i ++) cout << nm[i] << " ";
        cout << endl;
        return ;
    }
    for(int i = 0; i < 10; i ++)
    {
        if(d[i] > 0) 
        {
            nm[x] = i;
            d[i] --;
            dfs(x + 1);
            d[i] ++;
            nm[x] = 0;
        }
    }
    return ;
}

int main ()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> num[i];
        d[num[i]] ++;
    }
    dfs(0);
    return 0;
}

算法3

手动实现next_permutation函数（自然就有第四种直接用函数啦）

具体看注释

#include <bits/stdc++.h>

using namespace std;

const int mod = 1000000007;
typedef long long ll;
int num[20];
int n, k, idx, m;
string mm;

string next_arry(string x)
{
	 //找替换点
	string nm = x;
	bool hasNext = false;
    int i;
    for(i = nm.length() - 2; i >= 0; i --)
	{
        if(nm[i] < nm[i + 1])  // 找第一个递增数对
		{
            hasNext = true;
            break; //找到
        }
    }
    //如果所有元素是从大到小排列，说明是最大的字符串
    if(!hasNext) return mm;
         
    //从i+1的下标往后找（必定是单调递减）,在大于nm[i]的集合中找一个最小的元素
    int j;
    for(j = i + 1; j < nm.length(); j ++)
        if(nm[j] <= nm[i]) break;
    j--;
         
    //交换这两个元素，然后逆序i+1及以后的所有元素 [i+1,nm.length)
    swap(nm[i], nm[j]);
    
    //翻转子序列
    for(int io = i + 1, jo = n - 1; io < jo; io ++, jo --) swap(nm[io], nm[jo]);
    return nm;
}

int main ()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> num[i];
    sort(num + 1, num + 1 + n);
    string nm = "";
    for(int i = 1; i <= n; i ++) nm += (char)(num[i] + '0');
    for(int i = n; i > 0; i --) mm += (char)(num[i] + '0');
    while(nm < mm)
    {
        for(int i = 0; i < n; i ++) cout << nm[i] << " ";
        cout << endl;
        nm = next_arry(nm);
    }
    for(int i = 0; i < n; i ++) cout << mm[i] << " ";
    return 0;
}

第三种算法改编自csdn：

https://blog.csdn.net/bluecyan/article/details/103216555

三种算法最终时间分别是1084ms， 1062ms， 1076ms