问题:
输入N个0~9的整数,可以重复,从小到大打印出这N个数字组成的所有N位数。
e.g
输入:
4002
输出:
0024
0042
0204
0240
0402
0420
2004
2040
2400
4002
4020
4200
策略:
这道题是一个同学问我的,她帮一个同学完成作业。我刚看到问题的时候,第一个想法就是求出全排列,时间复杂度是O(n!)。写个算法除去重复的数列,再写一个算法排序,一个排序算法比如快速排序的平均时间复杂度O(n*lg n)。但也立马否定了。这个算法在整数个数增加后空间复杂度、时间复杂度都会有巨大的增长。这个算法好理解,但也不够巧妙。
其实可以考虑可以在寻找全排列的时候就可以以升序的顺序输出。因为升序数列数字的排列是有规律的。看下面的升序数列:
2345(1)
2354 (2)5提前到第3位
2435 (3)在(1)数列基础上4提前到第2位
2453 (4)5提前了一个位置,似乎是(1)~(2)过程的重复
2534 (5)在(1)数列的基础上将5提前到第2位
2543 (6)4提前了一个位置,似乎是(1)~(2)过程的重复,(5)~(6)似乎是(3)~(4)过程的重复
3245 (7)在(1)数列基础上将3提前到第1位
3254 (8)5提前了一个位置,似乎是(1)~(2)过程的重复
3425 (9)在(7)数列的基础上将4提前到第2位
3452 (10)将5提前到第3位,似乎是(1)~(2)过程的重复,(9)~(10)似乎是(3)~(4)过程的重复
3524 (11)在(7)数列基础上将5提前到第2位
3542 (12)将4提前到第3位,似乎是(1)~(2)过程的重复,(11)~(12)似乎是(3)~(4)过程的重复
4235 (13)在(1)数列的基础上将4提前到第一位
4253 (14)5提前了一个位置,似乎是(1)~(2)过程的重复
4325 (15)在(13)数列基础上将3提前到第2位
4352 (16)将5提前到第3位,似乎是(1)~(2)过程的重复,(15)~(16)似乎是(3)~(4)过程的重复
4523 (17)在(13)数列基础上将5提前到第2位
4532 (18)将3提前到第3位,似乎是(1)~(2)过程的重复,(17)~(18)似乎是(3)~(4)过程的重复,(13)~(18)似乎是(7)~(11)过程的重复
5234 (19)在(1)数列的基础上将5提前到第一位
5243 (20)4提前了一个位置,似乎是(1)~(2)过程的重复
5324 (21)在(19)数列基础上将3提前到第2位
5342 (22)将4提前到第3位,似乎是(1)~(2)过程的重复,(21)~(22)似乎是(3)~(4)过程的重复
5423 (23)在(19)数列基础上将4提前到第2位
5432 (24)将3提前到第3位,似乎是(1)~(2)过程的重复,(23)~(24)似乎是(3)~(4)过程的重复,(19)~(24)似乎是(7)~(11)过程的重复
各位睿智的看官,看出来否?存在一个策略分解这个问题成小问题,而对于每个分解问题存在一个通用的策略击破!对了,睿智如您,这就是分而治之的策略!将它问题分解成更小的问题,再分解成更小的问题。
(1)(2)是子数列4 5的全排列。
(1)~(6)是子数列3 4 5的全排列。(1)(2),(3)(4),(5)(6)分别是子数列3 5,3 4,4 5的全排列。
(1)~(24)是数列2 3 4 5的全排列。(1)~(6),(7)~(12),(13)~(18),(19)~(24)分别是3 4 5,2 4 5,2 3 5,2 3 4的全排列。下面就不列举了额。。。
思考即可发现,对每个输入的子数列,一个通用策略是:
1.从输入数列的倒数第二位作为当前位置开始到子数列开始处结束,迭代执行第2步。
2.在当前位置之后选择一个合适的数字提前到当前位置。(选择数字的策略下面有描述)
3.将当前位置之后的子数列作为输入,转入第1步,寻求子数列的全排列。
这是一个间接的递归调用,程序开始需要先将原始顺序混乱的数列进行升序排序,之后作为输入,调用第1步。可以发现,整个算法中子数列(注意此处指提前操作之后当前位置之后的数列)在调用第1步时始终保持升序有序,以保证最后的输出保持从小到大升序排列)。
注意是提前,不是交换,即不改变当前位置之后的升序顺序。
认真看下这个过程,便可以发现一个选择到提前到当前位置数字的策略。选择之前数列在当前位置之后总是升序排列的。为了使打印出的数列保持升序,选择提前数字时应当从小到大选择。然后将交换之后的目前位置之后的子数列递归调用,进行对它的全排列。还应该考虑数列中出现重复数字的情况。在选择数字时,应当保证提前到当前位置的数字和当前位置并且和前一个选择的数字不同。这样可以避免重复数列的出现。
每次提前数字应当在备份上进行处理,否则会造成混乱,违反了始终保持子数列升序有序的原则。其实当N增大到很大时,其全排列的数目是惊人的,运行会有种刷屏的感觉,:-)。其空间复杂度和时间复杂度是很高的。
实现(C语言):
测试结果:
输入为4002时:
输入为23372时:
输入为1736542时(部分输出):
算法分析:
算法中长度为n的子数列中next_arrangement的调用次数的递推公式A(n)=n*[A(n-1)+A(n-2)+...+A(2)]+1。A(2)=1(n>2)。total(n)=A(n)+A(n-1)+...+A(2)。total(n)也即为空间复杂度。这个是小于n!的。结果还在研究。。。
算法中主要的工作是复制数组和提前数字,平均提前的幅度是n/2(姑且这么搞哇。。。)。那么时间复杂度就是(3/2)*n*total(n)。
分享到:
相关推荐
组合数学全排列字典序法组合数学全排列字典序法组合数学全排列字典序法组合数学全排列字典序法组合数学全排列字典序法组合数学全排列字典序法组合数学全排列字典序法组合数学全排列字典序法
如:n=3 全排列的数字为 1 2 3 则输出 123 132 213 231 321 312 2、输入n和k(n》=k)求n个数字的(n,k)排列 如n=3,k=2 输入的三个数位1 2 3 则输出 12 13 21 23 31 32 3、输入n个数(有重复),求n个数字的...
供大家参考参考,代码还有改进的空间的.这里的排列输出是按照字典序的~~
使用递归 :-------------输入给出正整数n,输出1到n的全排列,排列的输出顺序为字典序,每种排列占一行,数字间无空格,
全排列生成算法中的字典序法的vc++源码
题目描述:给定一个数列a1,a2,a3…an,输出他所有的全排列。 算法设计描述: 1、获取当前的一种排列,用start,end分别表示该排列的列头,列尾; 2、判断start是否和end相等,若相等,执行3,否则执行4; 3、将当前...
c++全排列算法,输入一组数显示其所有可能顺序的序列
输出n个整数的全排列 C++程序 数据结构 实验一
全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1, 2, 3, 4, 5}为 例说明如何编写全排列的递归算法。 1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列...
输出n的全排列,有两种方法: 1. 采用递归插入的方法,如果知道n-1的全排列,n的全排列为将数值n插入的n-1的全排列之间的空隙和两头共n个位置。 2. 采用递归标记填充的方法,查看标记数组,将未标记的数值依次填充...
由1~n组成的所有不重复的数字序列,每行一个序列。 Sample Input 3 Sample Output 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Source elba 程序如下 const maxn=1000; var a:array[0..maxn] of longint; n,k:long...
算法分析课程作业,C语言编写,可能需要用input.txt输入,有重复数字的全排列代码
大家都知道对一个字符串进行排列是一个NP难问题,解决起来其实非常简单,只需要进行深度递归,将后面位置的数字或字符与基位置的进行调换,再选择输出即可!
使用Visual C++ 6.0开发,程序可以实现n个数的全排列的输出,比如对于1,2,3的全排列的输出为:123,132,213,231,312,321 程序采用递归的方式实现
如果一个长度为 n 序列包含 1 到n的每一个数字,那么我们说这个序列是一个长度为 n 的全排列。现给定一个长度为 n-1 由U 和D 构成的字符串,要求你构造一个字典序最小的全 排列 a,使其满足: 1.若第i 个字符是U,...
输出自然数1到n的所有不重复的排列,即n的全排列。
输出有重复字符的全排列,C++源码......
算法课写的小程序,在字典序下对输出序列的全排列
易语言数字文本的全排列源码,数字文本的全排列,取子串组合
易语言数字文本的全排列.rar