文档章节

算法之排列组合算法

mskk
 mskk
发布于 2017/05/04 21:22
字数 1388
阅读 5
收藏 0

转自<http://dongxicheng.org/structure/permutation-combination/>

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的全排列的组合.

#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。

下面是递归方法的实现:

/// 求从数组a[1..n]中任选m个元素的所有组合。
 
/// a[1..n]表示候选集,n为候选集大小,n>=m>0。
 
/// b[1..M]用来存储当前组合中的元素(这里存储的是元素下标),
 
/// 常量M表示满足条件的一个组合中元素的个数,M=m,这两个参数仅用来输出结果。
 
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                     // m == 1, 输出一个组合
 
    {
 
      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 1 1 0 0 //1,2,3
 
1 1 0 1 0 //1,2,4
 
1 0 1 1 0 //1,3,4
 
0 1 1 1 0 //2,3,4
 
1 1 0 0 1 //1,2,5
 
1 0 1 0 1 //1,3,5
 
0 1 1 0 1 //2,3,5
 
1 0 0 1 1 //1,4,5
 
0 1 0 1 1 //2,4,5
 
0 0 1 1 1 //3,4,5
 

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

原创文章,转载请注明: 转载自董的博客

本文链接地址: http://dongxicheng.org/structure/permutation-combination/

作者:Dong,作者介绍:http://dongxicheng.org/about/

本博客的文章集合:http://dongxicheng.org/recommend/

本文转载自:http://gaylord.iteye.com/blog/2114426

共有 人打赏支持
mskk
粉丝 3
博文 152
码字总数 3099
作品 0
昆山
程序员
智慧航空AI大赛-阿里云算法大赛总结 第一赛季总结

【以前的文章】最后一公里极速配送 - 阿里云算法大赛总结 总结一下新的教训 1.由于都是NP难题,获得最优解用常规的方法非常困难,对于不是算法科班出身的人来说,首先应该到网络上寻找一下论...

codesnippet.info
2017/08/01
0
0
PostgreSQL 遗传学应用 - 矩阵相似距离计算 (欧式距离,...XX距离)

标签 PostgreSQL , 背景 生物科学中相当重要的工作之一解开遗传密码? 欧式空间计算,是其中的一个需求,很有意思吧,PostgreSQL可以用来解开遗传密码。 https://en.wikipedia.org/wiki/Eucl...

德哥
2017/12/27
0
0
程序员必备算法——排列组合

程序员必备算法——排列组合 [TOC] 还记得排列组合吗? 在高中的时候最常接触的莫过于排列组合了,毕竟高考必考的嘛。我们先来回忆下这两个的公式是啥: 如果看到这个还有一丢丢的印象,说明...

窗边的扁豆
2017/10/07
0
0
next_permutation(全排列算法)

STL提供了两个用来计算排列组合关系的算法,分别是nextpermutation和prevpermutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所组成的序列{a,...

angel_kitty
2017/02/12
0
0
如何知道某个组合是否是一个排列组合中的一员

目标是如何知道某个组合是否是一个排列组合中的一员,有什么好的算法?例如C(4,10),如何知道组合1,2,3,4在这个排列中? @宏哥 @中山野鬼

技术揣摩
2013/09/27
128
4

没有更多内容

加载失败,请刷新页面

加载更多

原型模式

1、原型模式-定义 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象 克隆(浅度克隆->拷贝值类型或者引用,深度克隆->创建新的对象,开辟新的内存) 例如客户端知道抽象Pro...

阿元
今天
16
0
awk命令扩展使用操作

awk 中使用外部shell变量 示例1 [root@centos01 t1022]# A=888[root@centos01 t1022]# echo "" | awk -v GET_A=$A '{print GET_A}'888[root@centos01 t1022]# echo "aaaaaaaaaaaaa" | aw......

野雪球
今天
16
0
深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
今天
23
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
14
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部