首页 > 代码库 > 基于字典序的组合生成算法

基于字典序的组合生成算法

基于字典序的组合生成算法  

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 验证前述假设
 145234   验证前述假设
 234235   验证前述假设
 235245   验证前述假设
 245345   验证前述假设

   

 

 归纳结论:

⑴ 字典序生成算法中,集合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); //屏幕输出   }}