算法之排列算法与组合算法详解

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.jb51.net/article/54441.htm
(2) http://www.jb51.net/article/54443.htm
(3) 组合算法

本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标代表的数被选中,为0则没选中。

首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。

然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为 “01”组合,同时将其左边的所有“1”全部移动到数组的最左端。

当第一个“1”移动到数组的m-n的位置,即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

(0)

相关推荐

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • 浅谈c语言中一种典型的排列组合算法

    c语言中的全排列算法和组合数算法在实际问题中应用非常之广,但算法有许许多多,而我个人认为方法不必记太多,最好只记熟一种即可,一招鲜亦可吃遍天 全排列: #include<stdio.h> void swap(int *p1,int *p2) { int t=*p1; *p1=*p2; *p2=t; } void permutation(int a[],int index,int size) { if(index==size) { for(int i=0;i<size;i++) print

  • 排列和组合算法的实现方法_C语言经典案例

    排列和组合算法是考查递归的常见算法,这两种算法能用递归简洁地实现. 本人在经过多次摸索和思考之后,总结如下,以供参考. 程序代码如下: #include <stdio.h> #include <stdlib.h> char array[] = "abcd"; #define N 4 #define M 3 int queue[N] = {0}; int top = 0; int flag[N] = {0}; void perm(int s, int n) { i

  • js-FCC算法-No repeats please字符串的全排列(详解)

    把一个字符串中的字符重新排列生成新的字符串,返回新生成的字符串里没有连续重复字符的字符串个数.连续重复只以单个字符为准 例如, aab 应该返回 2 因为它总共有6中排列 (aab, aab, aba, aba, baa, baa),但是只有两个 (aba and aba)没有连续重复的字符 (在本例中是 a). 从网上资料获得了一些思路,我的代码: function permAlone(str) { var arr=str.split(""); var perarr=[]; var

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • Python实现K-means聚类算法并可视化生成动图步骤详解

    K-means算法介绍 简单来说,K-means算法是一种无监督算法,不需要事先对数据集打上标签,即ground-truth,也可以对数据集进行分类,并且可以指定类别数目 牧师-村民模型 K-means 有一个著名的解释:牧师-村民模型: 有四个牧师去郊区布道,一开始牧师们随意选了几个布道点,并且把这几个布道点的情况公告给了郊区所有的村民,于是每个村民到离自己家最近的布道点去听课. 听课之后,大家觉得距离太远了,于是每个牧师统计了一下自己的课上所有的村民的地址,搬到了所有地址的中心地带,并且在海

  • Go Java算法之外观数列实现方法示例详解

    目录 外观数列 方法一:遍历生成(Java) 方法二:递归(Go) 外观数列 给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数

  • Go Java算法之Excel表列名称示例详解

    目录 Excel表列名称 方法一:数学(Java) 方法一:数学(Go) Excel表列名称 给你一个整数 columnNumber ,返回它在 Excel 表中相对应的列名称. 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 示例 1: 输入:columnNumber = 1 输出:"A" 示例 2: 输入:columnNumber = 28 输出:"AB"

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • JS 面向对象之继承---多种组合继承详解

    这一次要讲 组合.原型式.寄生式.寄生组合式继承方式. 1. 组合继承:又叫伪经典继承,是指将原型链和借用构造函数技术组合在一块的一种继承方式. 下面来看一个例子: function SuperType(name) { this.name = name; this.colors = ["red", "blue", "green"]; } SuperType.prototype.sayName = function() { alert(this.n

  • JavaScript组合继承详解

    目录 1.前言 2.原型链继承 3.构造函数继承 4.组合继承 1.前言 首先学习继承之前,要对原型链有一定程度的了解. 不了解可以去先阅读我另一篇文章,里面对原型链有一个较为详细的说明:JavaScript 原型链详解. 如果已经了解请继续. 之前写过一篇博文将继承方式全部列出来了,不过我发现一口气看完过于长了,也不利于吸收知识,所以我先将组合继承部分划分出来,后续会把寄生部分补上. 2.原型链继承 父类实例作为子类的原型 子类创造的两个实例的隐式原型__proto__指向父类的那个实例 而父

  • Pandas搭配lambda组合使用详解

    导入模块与读取数据 我们第一步需要导入模块以及数据集 import pandas as pd df = pd.read_csv("IMDB-Movie-Data.csv") df.head() 创建新的列 一般我们是通过在现有两列的基础上进行一些简单的数学运算来创建新的一列,例如 df['AvgRating'] = (df['Rating'] + df['Metascore']/10)/2 但是如果要新创建的列是经过相当复杂的计算得来的,那么lambda方法就很多必要被运用到了,我们先

  • Python组合数据类型详解

    目录 集合 元组 创建方式 列表 操作函数 操作方法 列表的引用 字典 查找 修改和添加 字典的操作函数 字典的操作方法 集合 创建集合有两种方式: 第一种: T = {11,111,"11"} print(T) # {'11', 111, 11} 第二种: T = set("Hello Would") print(T) {'H', 'e', 'o', ' ', 'l', 'd', 'u', 'W'}  注意: 1.如果创建空集合必须使用第二种方法. 2.集合中元素

随机推荐