文档章节

算法之排列组合算法

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
博文 158
码字总数 3371
作品 0
昆山
程序员
私信 提问
PostgreSQL 遗传学应用 - 矩阵相似距离计算 (欧式距离,...XX距离)

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

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

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

窗边的扁豆
2017/10/07
0
0
智慧航空AI大赛-阿里云算法大赛总结 第一赛季总结

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

codesnippet.info
2017/08/01
0
0
如何知道某个组合是否是一个排列组合中的一员

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

技术揣摩
2013/09/27
150
4
next_permutation(全排列算法)

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

angel_kitty
2017/02/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

logback.xml 配置

需要引入 logback-core-1.1.2.jar <?xml version="1.0" encoding="UTF-8"?><configuration debug="false"> <!--定义日志文件的存储地址 勿在 LogBack 的配置中使用相对路径 --> ......

夜醒者
12分钟前
1
0
Java 11 已发布,String 还能这样玩!

在文章《Java 11 正式发布,这 8 个逆天新特性教你写出更牛逼的代码》中,我有介绍到 Java 11 的八个新特性,其中关于 String 加强部分,我觉得有点意思,这里单独再拉出来讲。 Java 11 增加...

Java技术栈
36分钟前
6
0
什么是以太坊DAO?(二)

Decentralized Autonomous Organization,简称DAO,以太坊中重要的概念。一般翻译为去中心化的自治组织。 在上一节中,我们为了展示什么是DAO创建了一个合约,就像一个采用邀请制的俱乐部,会...

geek12345
52分钟前
4
0
全屋WiFi彻底无死角 这才是终极解决方案

无线网络现在不仅在家庭中不可或缺,在酒店、医院、学校等场景中的需求也越来越多。尤其是这些场景中,房间多但也需要每个房间都能够完美覆盖WiFi,传统的吸顶式AP就无法很好的解决问题。 H3...

linux-tao
今天
6
0
Python日期字符串比较

需要用python的脚本来快速检测一个文件内的二个时间日期字符串的大小,其实实现很简单,首先一些基础的日期格式化知识如下 复制代码 %a星期的简写。如 星期三为Web %A星期的全写。如 星期三为...

dragon_tech
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部