1. 前言
本文介绍了常用的排列组合算法,包括全排列算法,全组合算法,m个数选n个组合算法等。
2. 排列算法
常见的排列算法有:
(A)字典序法
(B)递增进位制数法
(C)递减进位制数法
(D)邻位对换法
(E)递归法
介绍常用的两种:
(1) 字典序法
对给定的字符集中的字符规定了一个先后关系,在此基础上按照顺序依次产生每个排列。
[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。
生成给定全排列的下一个排列 所谓一个的下一个就是这一个与下一个之间没有字典顺序中相邻的字符串。这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。
算法思想:
设P是[1,n]的一个全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn , j=max{i|Pi<Pi+1}, k=max{i|Pi>Pj} ,对换Pj,Pk,将Pj+1…Pk-1PjPk+1…Pn翻转, P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个
例子:839647521的下一个排列.
从最右开始,找到第一个比右边小的数字4(因为4<7,而7>5>2>1),再从最右开始,找到4右边比4大的数字5(因为4>2>1而4<5),交换4、5,此时5右边为7421,倒置为1247,即得下一个排列:839651247.用此方法写出全排列的非递归算法如下
该方法支持数据重复,且在C++ STL中被采用。
(2) 递归法
设一组数p = {r1, r2, r3, … ,rn}, 全排列为perm(p),pn = p – {rn}。则perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。当n = 1时perm(p} = r1。
如:求{1, 2, 3, 4, 5}的全排列
1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
由于一个数的全排列就是其本身,从而得到以上结果。
2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <stdio.h>
int n = 0;
void swap( int *a, int *b)
{
int m;
m = *a;
*a = *b;
*b = m;
}
void perm( int list[], int k, int m)
{
int i;
if (k > m)
{
for (i = 0; i <= m; i++)
printf ( "%d " , list[i]);
printf ( "\n" );
n++;
}
else
{
for (i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
}
}
int main()
{
int list[] = {1, 2, 3, 4, 5};
perm(list, 0, 4);
printf ( "total:%d\n" , n);
return 0;
}
|
3. 组合算法
3.1 全组合
在此介绍二进制转化法,即,将每个组合与一个二进制数对应起来,枚举二进制的同时,枚举每个组合。如字符串:abcde
00000 <– –> null
00001<– –> e
00010 <– –> d
… …
11111 <– –> abcde
3.2 从n中选m个数
(1) 递归
a. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止。
b. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m。
下面是递归方法的实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
void combine( int a[], int n, int m, int b[], const int M )
{
for ( int i=n; i>=m; i--)
{
b[m-1] = i - 1;
if (m > 1)
combine(a,i-1,m-1,b,M);
else
{
for ( int j=M-1; j>=0; j--)
cout << a[b[j]] << " " ;
cout << endl;
}
}
}
|
(2) 01转换法
本程序的思路是开一个数组,其下标表示1到n个数,数组元素的值为1表示其代表的数被选中,为0则没选中。
首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的n-m的位置,即n个“1”全部移动到最右端时,就得到了最后一个组合。
例如求5中选3的组合:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
1 1 1 0 0
1 1 0 1 0
1 0 1 1 0
0 1 1 1 0
1 1 0 0 1
1 0 1 0 1
0 1 1 0 1
1 0 0 1 1
0 1 0 1 1
0 0 1 1 1
|
4. 参考资料
(1) http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html
(2) http://comic.sjtu.edu.cn/thucs/GD_jsj_025y/text/chapter01/sec05/default.htm
(3) http://blog.csdn.net/sharpdew/archive/2006/05/25/755074.aspx
(4) http://xiaomage.blog.51cto.com/293990/74094
分享到:
相关推荐
主要介绍了C#实现排列组合算法的完整实例,文中实例主要展示了排列循环方法和排列堆栈方法,需要的朋友可以参考下
该文档对排列组合问题的算法设计问题进行一系列讲述
组合数学之排列组合生成算法,很好的学习组合排列算法的资料
excel VBA - 排列组合生成算法 - ,可快速生成指定项目的所有排列组合
PHP实现多种类型的排列组合算法,PHP多种方式实现排列组合算法。非常有用,欢迎下载。
将一组数字、字母或符号进行排列,以得到不同的组合顺序,例如1 2 3这三个数的排列组合有:1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。
排列组合 排列 组合 java排列组合算法 排列组合算法
排列组合算法实现,支持模板类。支持重复数的排列。算法采用递归方法,简单易懂。
排列组合算法排列组合算法.doc
交换算法得到全排列,排列组合的全排列算法(交换算法)
C++数学与算法系列之排列和组合
本资源附带文档解释了排列组合算法的实现和原理。其中排列算法是基于递归实现的,组合算法是基于高效的位移法实现的。代码是使用Java版实现的。
c++课程设计,排列组合,算法 超级简单的,
本程序是排列组合算法的c语言表示,使用递归实现
Java排列组合算法
第十一章 组合优化算法与计算的时间复杂度理论 11.1 dijkstra算法 11.2 floyd算法 11.3 kruskal算法 11.4 求最优树的破圈法和统观法 11.5 二分图中最大匹配与最佳匹配的算法 11.6 fleury算法 11.7 ...
Java排列组合算法 - 郭睿的专栏 - CSDN博客Java排列组合算法 - 郭睿的专栏 - CSDN博客
用VC++6.0编写的排列组合生成算法,对算法有兴趣的朋友可以看看,并欢迎与我交流
排列组合生成算法的python实现。实现方法参考了维基百科中的combination和permutation词条。 使用方法: python combinations.py #按字典序生成6中选3的组合(数字代码中可以调整) python arrangement.py #按字典序...