【C++】无重复数字全排列(三种方法)和有重复数字全排列

这篇具有很好参考价值的文章主要介绍了【C++】无重复数字全排列(三种方法)和有重复数字全排列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


一、无重复数字排列

1.1 题目描述

 把 1 ∼ n 1∼n 1n n n n 个整数排成一行后随机打乱顺序,输出所有可能的次序。

输入格式:
一个整数 n n n 1 ≤ n ≤ 9 1≤n≤9 1n9
输出格式:
按照从小到大的顺序输出所有方案,每行 1 1 1 个。
首先,同一行相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。

1.2 用dfs方法

1.2.1 思路分析

 1. 这个问题其实就是求无重复元素的全排列,经典的 d f s dfs dfs 题。 d f s dfs dfs 最重要的是搜索顺序,用什么顺序遍历所有方案。对于全排列问题,以 n = 3 n = 3 n=3 为例,可以这样进行搜索:
【C++】无重复数字全排列(三种方法)和有重复数字全排列,计算机算法分析与设计第五版(王晓东),c++,深度优先,回溯法
 假设有 3 个空位,从前往后填数字,每次填一个位置,填的数字不能和前面一样。

 最开始的时候,三个空位都是空的:__ __ __

 首先填写第一个空位,第一个空位可以填 1,填写后为:1 __ __

 填好第一个空位,填第二个空位,第二个空位可以填 2,填写后为:1 2 __

 填好第二个空位,填第三个空位,第三个空位可以填 3,填写后为: 1 2 3

这时候,空位填完,无法继续填数,所以这是一种方案,输出。

 然后往后退一步,退到了状态:1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ,没有其他数字可以填。

 因此再往后退一步,退到了状态:1 __ __。第二个空位上除了填过的 2,还可以填 3。第二个空位上填写 3,填写后为:1 3 __

 填好第二个空位,填第三个空位,第三个空位可以填 2,填写后为: 1 3 2

这时候,空位填完,无法继续填数,所以这是一种方案,输出。

 然后往后退一步,退到了状态:1 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2,没有其他数字可以填。

 因此再往后退一步,退到了状态:1 __ __。第二个空位上除了填过的 2,3,没有其他数字可以填。

 因此再往后退一步,退到了状态:__ __ __。第一个空位上除了填过的 1,还可以填 2。第一个空位上填写 2,填写后为:2 __ __

 填好第一个空位,填第二个空位,第二个空位可以填 1,填写后为:2 1 __

 填好第二个空位,填第三个空位,第三个空位可以填 3,填写后为:2 1 3

这时候,空位填完,无法继续填数,所以这是一种方案,输出。

 然后往后退一步,退到了状态:2 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3,没有其他数字可以填。

 因此再往后退一步,退到了状态:2 __ __。第二个空位上除了填过的 1,还可以填 3。第二个空位上填写 3,填写后为:2 3 __

 填好第二个空位,填第三个空位,第三个空位可以填 1,填写后为:2 3 1

这时候,空位填完,无法继续填数,所以这是一种方案,输出。

 然后往后退一步,退到了状态:2 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1,没有其他数字可以填。

 因此再往后退一步,退到了状态:2 __ __。第二个空位上除了填过的 1,3,没有其他数字可以填。

 因此再往后退一步,退到了状态:__ __ __。第一个空位上除了填过的 1,2,还可以填 3。第一个空位上填写 3,填写后为:3 __ __

 填好第一个空位,填第二个空位,第二个空位可以填 1,填写后为:3 1 __

 填好第二个空位,填第三个空位,第三个空位可以填 2,填写后为:3 1 2

这时候,空位填完,无法继续填数,所以这是一种方案,输出。

 然后往后退一步,退到了状态:3 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2,没有其他数字可以填。

 因此再往后退一步,退到了状态:3 __ __。第二个空位上除了填过的 1,还可以填 2。第二个空位上填写 2,填写后为:3 2 __

 填好第二个空位,填第三个空位,第三个空位可以填 1,填写后为:3 2 1

这时候,空位填完,无法继续填数,所以这是一种方案,输出。

 然后往后退一步,退到了状态:3 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1,2,没有其他数字可以填。

 因此再往后退一步,退到了状态:3 __ __。第二个空位上除了填过的 1,2,没有其他数字可以填。

 因此再往后退一步,退到了状态:__ __ __。第一个空位上除了填过的 1,2,3,没有其他数字可以填。

此时深度优先搜索结束,输出了所有的方案。

输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

时间复杂度为 O ( n ∗ n ! ) O(n*n!) O(nn!)

1.2.2 代码编写

 用 p a t h path path 数组保存排列,当排列的长度为 n n n 时,是一种方案,输出。
 用 s t a t e state state 数组表示数字是否用过。当 s t a t e [ i ] state[i] state[i] 1 1 1 时: i i i 已经被用过, s t a t e [ i ] state[i] state[i] 0 0 0 时, i i i 没有被用过。
d f s ( i ) dfs(i) dfs(i) 表示的含义是:在 p a t h [ i ] path[i] path[i] 处填写数字,然后递归的在下一个位置填写数字。
 回溯:第 i i i 个位置填写某个数字的所有情况都遍历后, 第 i i i 个位置填写下一个数字。

#include<iostream>
using namespace std;
const int N = 10;
int path[N];  //保存序列
int state[N]; //数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了,输出
    {
        for(int i = 1; i <= n; i++) //输出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++) //空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])    //如果数字 i 没有被用过
        {
            path[u] = i; //放入空位
            state[i] = 1;//数字被用,修改状态
            dfs(u + 1);  //填下一个位
            state[i] = 0;//回溯,取出 i
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);
    return 0;
}

1.3 用交换法

 交换法思想就是定下一个前缀,然后将后面的数全排列。

#include<iostream>
using namespace std;
int n;
//int cnt = 0; cnt用来计数的 
void Permutation(int *s,int p) //从数组s的第p个位置开始全排列
{
    if(p==n)
    {
        for(int i=0;i<n;i++) 
        {
        	cout<<s[i];
	    }
	    cout<<endl;
        //可计数有多少种排序cnt++;
    }
    for(int i=p;i<n;i++)
    {
        swap(s[i],s[p]);  //每个字符都有成为当前起始字符的机会
        Permutation(s,p+1);
        swap(s[i],s[p]);  //返回初始状态,才能保证后面的交换是正确的,回溯
    }
}
int main()
{
	cin>>n;
    int s[n];
    for(int i=0;i<n;i++) 
    {
    	s[i]=i+1;
	}
    Permutation(s,0);
    //cout <<cnt << endl; 可输出有多少中排序 
    return 0;
}

1.4 STL秒解

1.4.1 所用函数

 1. next_permutation的功能是生成给定序列的下一个字典序排列。这个函数在C++ STL中,对于解决排列组合问题和迭代遍历所有可能排列时非常有用。
 2. prev_permutation的功能是生成给定序列的前一个字典序排列。这个函数在C++ STL中,可以用于迭代遍历所有可能的排列,与next_permutation相反,它是从大到小的顺序生成排列。

1.4.2 代码编写

#include <iostream>
#include<algorithm> //头文件
using namespace std;
int main()
{
	int n;
	cin>>n;
    int s[n];
    for(int i=0;i<n;i++) 
    {
    	s[i]=i+1;
	}
    //int cnt = 0;
    do
    {
        for(int i=0;i<n;i++) 
        {
        	cout<<s[i];
	    }
	    cout<<endl;
    }while(next_permutation(s,s+n));//起始位置,左闭右开
    
    //cout<<"总共有:"<<cnt<<" 种排列"<<endl;
    return 0;
}

二、有重复数字排列

2.1 思路分析

 1. 看到这个题目首先能想到的一点就是:(1) 我们要求元素的所有全排列。(2) 我们要对求出的全排列去重。

 2. 求全排列用交换递归;去重我们可以设计一个函数来判断这个元素是否前面已经用到过了。

2.2 代码编写

#include <iostream>
using namespace std;
int count=0;
void swap(char &a,char &b)
{
	char temp;
	temp=a;
	a=b;
	b=temp;
}
int finish(char list[],int k,int i)
{   //第i个元素是否在前面元素[k...i-1]中出现过
	if(i>k)
	{
		for(int j=k;j<i;j++)
			if(list[j]==list[i])
				return 0;
	}
	return 1;
}
void perm(char list[],int k,int m)
{
	if(k==m)    //当只剩下一个元素时则输出
	{
		count++;
		for(int i=0;i<=m;i++)
			cout<<list[i];
		cout<<endl;
	}
	for(int i=k;i<=m;i++)  //还有多个元素待排列,递归产生排列
	{
		if(finish(list,k,i))
		{
			swap(list[k],list[i]);
			perm(list,k+1,m);
			swap(list[k],list[i]);
		}
	}
}
int main()
{
	int i,n;
	cout<<"请输入元素个数: "<<endl;
	cin>>n;
	cout<<"请输入待排列的元素: "<<endl;
	//getchar();
	char *a=new char[n];
 
	for(i=0;i<n;i++)
		cin>>a[i];
	cout<<"所有不同排列为: "<<endl;
	perm(a,0,n-1);
	cout<<"排列总数为: "<<count<<endl;
	return 0;
}

【C++】无重复数字全排列(三种方法)和有重复数字全排列,计算机算法分析与设计第五版(王晓东),c++,深度优先,回溯法文章来源地址https://www.toymoban.com/news/detail-739909.html

到了这里,关于【C++】无重复数字全排列(三种方法)和有重复数字全排列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【无重复字符的最长子串--三种方法】

    大家好,今天我们来讨论一下LeetCode上两道数组方面的例题来为大家讲解滑动窗口的使用。 题目不难,方法很多。熊猫希望通过第一道简单的题目来使大家了解到不同的解题方法。 题目描述:给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 点击跳转

    2024年01月18日
    浏览(33)
  • Python 判断列表里是否有重复元素的三种方法

    一、用 set 方法去重后与原列表长度比较 二、用 append 的方式把原列表中的元素添加到一个新列表,确保新列表里不存在重复的元素,然后比较两个列表 三、用 fromkeys 的方法创建一个字典,因为字典的键会自动去重,所以可以比较字典和原列表的长度,跟方法一很像

    2024年02月11日
    浏览(55)
  • 符号三角形-计算机算法设计与分析【1600+字解析 dfs全排列 列举情况】【题意分析】【算法分析】【思路是怎么来的】【过程是什么】

    下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”,2个异号下面都是“-”。 在一般情况下,符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。 题意分析 也就是 给

    2024年02月03日
    浏览(36)
  • 安卓开发学习之设计三种计算机界面

    1.简单的计算器 2.科学计算器 3.程序计算器 不用实现具体功能,只需设计界面即可! 为了更好的在三个界面之间跳转,添加一个主界面。 activity_main.xml 线性布局中添加4个按钮 界面效果: 简单计算器: chengxujishuanqi.xml 界面效果: 科学计算器: kexuejishuanqi.xml 界面效果: 程序

    2023年04月08日
    浏览(47)
  • 为什么计算机对浮点型数字计算存在误差

    我们输入的十进制小数在计算机中都是以二进制进行存储。比如: 由此可见0.3在计算机中存储的值永远小于0.3,所以当使用0.3计算时,就会产生误差。 在计算机中浮点型不能直接使用等号比较也是同一个道理。举个李子: 执行结果: 可以看出当涉及到0.3的运算超出一定的精

    2023年04月11日
    浏览(47)
  • C++ STL第三篇(搞清楚deque原理和有多少用法)

    Vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,无法被接受。 Deque容器和vector容器最大的差异,

    2024年03月17日
    浏览(34)
  • 计算机数字编码入门篇(下)

    本文旨在为初学者提供有关计算机数字编码的基础知识,以帮助他们初步理解计算机中数字编码的概念。鉴于我个人知识的限制,如有不准确之处,欢迎指正并提供建议。 文中部分内容参考ChatGPT,在此感谢ppword的大力支持。 定点数,其关键地方就在“定”和“点”这两个字

    2024年02月08日
    浏览(33)
  • 【计算机组成原理】高速缓冲存储器 Cache 的三种映射方式(Cache Mapping)

    缓存是计算机系统中常见的一种高速存储器,用于临时存储常用数据,以便快速访问。在缓存中,有三种常见的映射方式,分别是直接映射、全相联映射和组相联映射。 在直接映射中,每个主存块只能映射到缓存中的一个特定位置。该位置是通过对主存块的某个地址的一部分

    2024年01月19日
    浏览(46)
  • 计算机视觉:窥探数字世界的眼睛

    目录 简介: 一. 计算机视觉的起源与发展 二. 计算机视觉的应用领域 三. 计算机视觉的挑战与未来发展 结论: 计算机视觉(Computer Vision)是人工智能(AI)领域中的一个重要分支,专注于研究如何使计算机系统能够“看见”、理解和解释图像和视频的技术。它旨在模拟人类

    2024年02月12日
    浏览(36)
  • 【计算机视觉】数字图像处理(四)—— 图像增强

    图像增强是采用一系列技术去改善图像的视觉效果,或将图像转换成一种更适合于人或机器进行分析和处理的形式。例如采用一系列技术有选择地突出某些感兴趣的信息,同时抑制一些不需要的信息,提高图像的使用价值。 图像增强方法 图像增强方法从增强的作用域出发,可

    2023年04月16日
    浏览(103)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包