文档章节

算法之排列组合算法

mskk
 mskk
发布于 2017/05/04 21:22
字数 1388
阅读 4
收藏 0
点赞 0
评论 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/

© 著作权归作者所有

共有 人打赏支持
mskk
粉丝 2
博文 145
码字总数 2246
作品 0
宝山
程序员
排列组合算法

1.组合算法 1.1 方法一 本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标 代表的数被选中,为0则没选中。 首先初始化,将数组前n个元素置1,表示第一个组合为前n个...

面码 ⋅ 2014/05/15 ⋅ 0

程序员必备算法——排列组合

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

窗边的扁豆 ⋅ 2017/10/07 ⋅ 0

PostgreSQL 遗传学应用 - 矩阵相似距离计算 (欧式距离,...XX距离)

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

德哥 ⋅ 2017/12/27 ⋅ 0

next_permutation(全排列算法)

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

angel_kitty ⋅ 2017/02/12 ⋅ 0

三种方法实现PCA算法(Python)

  主成分分析,即Principal Component Analysis(PCA),是多元统计中的重要内容,也广泛应用于机器学习和其它领域。它的主要作用是对高维数据进行降维。PCA把原先的n个特征用数目更少的k...

但盼风雨来_jc ⋅ 2017/12/12 ⋅ 0

如何知道某个组合是否是一个排列组合中的一员

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

技术揣摩 ⋅ 2013/09/27 ⋅ 4

60.Permutation Sequence-Leetcode

基础回顾 String 头文件中必须包括 string的声明初始化 遍历 string与char* 字符串连接 string与int转化(注意stringstream) 我的算法(受nextPermutation影响大,算法效率低) nextPermut...

analanxingde ⋅ 01/15 ⋅ 0

小学数学问题,在线急等

数字1,2 有组合【1】【2】【1,2】 数字1,2,3 有组合【1】【2】【3】【1,2】,【1,3】,【2,3】,【1,2,3】 有没有算法在给出一组数字的时候,做出以上排列组合...

OLESHI ⋅ 02/26 ⋅ 0

2018-01-9 记百度电话面试

自我介绍 聊项目相关 聊聊基础 stringbuffer,stringbuilder区别 jvm内存模型 GC算法,项目中实现的GC算法??(不会实现) 聊聊java的锁synchronize和lock,说说读写锁 说说spring的重要特性(ioc)...

芥末无疆sss ⋅ 01/10 ⋅ 0

小朋友学算法(7):求排列数和组合数

关于排列的介绍,可以参考小朋友学奥数(11):排列 关于组合的介绍,可以参考小朋友学奥数(12):组合 程序: 分析: 根据程序算法,  P(10, 3) = P(10, 2) 8 = P(10, 1) 9 8 = P(10, 0)...

翡翠森林Z ⋅ 2017/12/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

骰子游戏代码开源地址

因为阿里云现在服务器已经停用了,所以上面的配置已经失效。 服务端开源地址:https://gitee.com/goalya/chat4.git 客户端开源地址:https://gitee.com/goalya/client4.git 具体运行界面请参考...

算法之名 ⋅ 37分钟前 ⋅ 0

设计模式--装饰者模式

装饰者模式 定义 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比生成子类更为灵活。 通用类图 意图 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比...

gaob2001 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部