首页 > 代码库 > 基于字典序的组合生成算法
基于字典序的组合生成算法
基于字典序的组合生成算法
2010-12-02 01:22:52| 分类: 离散数学 | 标签:离散数学 排列组合 |举报 |字号大中小 订阅
一、 问题描述
给定非空集合A,按字典序的方法生成集合A的所有组合。关于字典序的概念,这里不做严格定义,只是做一简单解释。
字典序是字符串比较的一种方法。例如两个字符串 abcd,abef,这两个字符串谁大? 显然,abef>abcd;如何得出这个结论的呢? 从左至右依次比较每一个字符,首先比较两个串的第一个字符,都是a,相等;其次比较两个串的第二个字符,都是b,仍然相等;比较第三个字符,分别为c和e,c<e;所以abef>abcd.
二、问题分析
不失一般性,设A={1,2,3,4,5},生成A的所有3组合
A的所有3组合个数为C(5,3)=10 按字典序,其组合一次为:
{ 123,124,125,134,135,145,234,235,245,345 }
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩
请仔细观察每一个组合数的,为了观察方便,我已经将每一个组合编了号。
【特别注意:任意两个连续组合数之间有什么规律?】
为了分析方便,定义两个名词:当前组合数和下一个组合数。可以将任意编号为i的组合数作为当前组合数,那么下一个组合数就是编号为i+1的组合数。
当前组合数 | 下一个 组合数 | 由当前组合数生成下一个 组合数的方式 | 思维方法 |
123 | 124 | 最后一位的3+1 | 每一个组合的都是升序 |
124 | 125 | 最后一位的4+1 | 抽象出“位置”概念 |
125 | 134 | 生成124,125的规则不再适用,125的个位 数5是A中的最大元素,不可再加1,考虑十 位数,是2;前3为是13,第三位即各位数 字必须比十位数字大,比十位数3大的最小 数字是4,所以125的下一个组合是134 | ①抽象出每一位置的最大数概念 ②提出初步假设(规则) a.从左至右改变每一个位置 上的数字; b.如果个位位置上的数不可 改变,改变十位位置上的数 c.高位位置上的数字改变 后,低位位置上的数字依次 增加1 . |
134 | 135 | 134的最后一位4可以直接加1 | 验证前述假设 |
135 | 145 | 同125→134 | 验证前述假设 |
145 | 234 | 验证前述假设 | |
234 | 235 | 验证前述假设 | |
235 | 245 | 验证前述假设 | |
245 | 345 | 验证前述假设 |
归纳结论:
⑴ 字典序生成算法中,集合A必须是全序集合。
⑵每个组合由r个数字组成;
⑶形成两个概念:位置(各位、十位、百位……)、每个位置的最大数字
⑶从当前组合生成下一个组合时,首先变化个位数字,其次变化十位数上的位置;然后变化百位数上的位置,……
⑷个位数上的最大数字是n,十位数位置上的最大数是n-1,百位数位置上的最大数是n-2,……
⑸ 生成下一个组合数的规则
a.从左至右改变每一个位置上的 数字;
b.如果个位位置上的数不可改变,改变十位位置上的数
c.高位位置上的数字改变后,低位位置上的数字一次增加1 .
三、算法框架
为了编程,需要设置一些变量,即定义数据结构(这个过程称为建模)。
用数组s[]表示当前组合;用m表示当前位置;maxval表示当前位置上的最大值
① 初始时:当前位置m=r(个位); maxval=n(个位上的最大值)
②从左向右寻找可改变数字的位置;
while( maxval==n ){
m=m-1;
maxval=maxval-1;
}
这段代码执行后可改变数值的位置是m
③ 可改变数字的位置上的数字加1
s[m]=s[m]+1
④ 后续每一位在前一位的基础上加1
for(j=m+1;j<=r;j++)
s[j]=s[j-1]+1;
四、算法程序
#include<iostream>#include<stdio.h>void printc(int s[],int r){ for(int i=1;i<=r;i++) printf("%d",s[i]); //cout<<s[i]; printf("\n");}long fac(int n) //计算n的阶乘{ long f,i; f=1; for(i=1;i<=n;i++) f=f*i; return f;}void next_comb(int s[],int n,int r){ int j,m,max_val; max_val=n; m=r; while(s[m]==max_val) { m=m-1; max_val=max_val-1; } s[m]=s[m]+1; for(j=m+1;j<r;j++) s[j]=s[j-1]+1;}int main(){ int s[]={0,1,2,3}; //数组s表示生成的每一个组合,第一个组合是123 int n=5,r=3, cnr=10; printc(s,r); cnr=fac(n)/(fac(r)*fac(n-r)); for(int i=2;i<=cnr;i++) { next_comb(s,n,r); //生成当前组合的下一个组合 printc(s,r); //屏幕输出 }}