C语言名题精选百则——排列，组合与集合

DSQiu

浏览: 1397500 次
性别:
来自: 广州

最近访客更多访客>>

ymgjava

spike_wq

sdsunrunner

hackxboy

博主相关

博客

微博

相册

留言

关于我

博客专栏

: NGUI所见即所得
浏览量：195162

: Effective C# ...
浏览量：0

文章分类

社区版块

存档分类

博客分类：

C语言名题精选百则
问题解决

C语言名题精选百则——排列，组合与集合

尊重他人的劳动，支持原创

本篇博文，D.S.Qiu将对《C语言名题精选百则——排列，组合和集合》进行整理推出，不光只是书上的名题，还会依据互联网的资源进行不断补充，加强。等全书各个章节都整理完，会做一个总汇。如果你有建议、批评或补充，请你不吝提出（email:gd.s.qiu@gmail.com，或者直接在本文末评论）。你的支持和鼓励（一个人整理真的很累，几度想放弃），我将渐行渐远！

《排列，组合和集合》主要是介绍了关于集合的子集以及子集字典排序，Gray码，排列以及字典排列，集合的分割，整数的分割等8个组合数学基本的问题，介绍比较繁复（废话比较多），只要看了就能理解（点击查看更多数组和字符串问题），相对简单，但是要是尽善进美还有待不断的挖掘。下一篇是《查找》（其实关于有序数组的一些问题），更多关注：http://dsqiu.iteye.com。

问题3.1列出所有子集（DIRECT.C ）

编写一个程序，列出{1，2，3,…，n}这个集合的所有子集，包括空集合。

【说明】

列出一个集合的所有子集有很多做法，题目中并没有要求依某个特定的次序来排列，因此是不难做出来的。

因为集合中一共有n个元素，所以总共就会有2^n子集；例如{1，2，3}有如下子集：

{}

{1} {2} {3}

{1,2} {1,3} {2,3}

{1,2,3}

【解答】

看到2^n，就想起了二进制数，可以使用二进制的第 i 位表示是否包含集合的第 i 个元素，如数字6的二进制形式是110，表示取集合的第2,3两个元素组成的子集。这样0~2^n -1的数字就可以表示全部子集，每一个数字代表一个子集，实现应该不难。

【问题实现】

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE   20
#define   LOOP       1

void main(void)
{
     char digit[MAXSIZE];
     int  i, j;
     int  n;
     char line[100];

     printf("\nDirect Generation of All Subsets of a Set");
     printf("\n=========================================");
     printf("\n\nNumber of Elements in the Given Set --> ");
     gets(line);
     n = atoi(line);

     /* ---You'd better check to see if n is too large--- */

     for (i = 0; i < n; i++)  /* clear all digits to 0    */
          digit[i] = '0';

     printf("\n{}");          /* outpout empty set {}     */
     while (LOOP) {
          for (i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++)
               ;              /* find first 0 position    */
          if (i == n)         /* if none, all pos. are 1  */
               break;         /* thus all elem. are in set*/
          else
               digit[i] = '1';/* now add one to this pos  */

          for (i = 0; i < n && digit[i] == '0'; i++)
               ;              /* find first 1 position    */
          printf("\n{%d", i+1);  /* show its numner and   */
          for (j = i + 1; j < n; j++) /* others           */
               if (digit[j] == '1')
                    printf(",%d", j + 1);
          printf("}");
     }
}

问题3.2列出所有子集——字典顺序（LEXICAL.C ）

编写一个程序，用字典顺序（Lexical Order)把一个集合的所有子集找出来。

【说明】

如果不知道何谓字典顺序，在此作一个简单的说明。假设给定的集合有n个元素，

{1,2,3,4}与{1,2，4}是两集合，它们前面的两个元素相同，但第三个不同，因此包含小的元素的集合就排在前面。请回想一下，这与字符串的比较有什么不一样呢？完全相同，惟一的差异，就是在集合中的元素要从小到大排好。

下面左边是n=3,右边是n=4的结果，如表3-1所示。

【解答】

事实上，这是一个十分简单的程序，除了空集合之外，最“小”的一个集合就是{1}再下一个就是包含1,而且再加上1的下一个元素（1+1=2)的集合，即{1，2};下一个元素自然就是含有1与2,并且还有2的下一个元素（2+1=3)的集合{1，2，3}了。就这样一直到包含了所有元素为止，亦即{1,2,3，····，n}。下一个集合是谁？绝不是{1,2，3，…，n-1}，.因为它比{1,2，3，…，n}小，事实上应该是{1，2,3，…,n-2,n}。为什么呢？在{1，2，3，…，n-1，n}与 {1，2,3,…，n-2，n}之间，前n-2个元素完全相同，但是n-1<n,这不就证实了以上说法了吗？

由于以上原因，因此可以用一个数组set[]来存放集合的元素，一开始时set[0]=1,表示{1};另外，用一个变量position,指出目前最右边的位置何在，在开始时自然就是1。接下来，就陆续地产生下一个集合了。注意，目前集合中最右边的元素是set[position]，如果它的值比n小，那就表示还可以加进一个元素，就像是从{1，2，3}加上一个元素变成{1，2，3， 4}一样（n>4)。这倒是容易做，下一个元素在set[position+1]，因此在那存入set[position+1] 这个值就行了；同时position也向右移一位。如果目前最右边元素set [position]已经是n，因而不能再增加元素了。例如，当n=4时，如果有{1，3，4},那自然不能像前面所说的加入一个5。这时看最右边元素的位置，亦即position,是不是在第一位（如果n=6,而现在的集合是{6}),如果不在第一位，那就可以往回移一位，并且把那个位置的值加上1。例如，如果现在有{1，3，4}，而n=4;最右边（4）的位置不是在第一位，因而退回一位，等于是{1，3}; 但这是不对的，因为{1，3}比{1，3，4} “小”，要做得比{1，3，4}大，把3加上1而变成{1，4}就行了。如果最右边（4)的位置是在第一位，那么程序就完成了。

【问题实现】

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE      20
#define   LOOP          1

void main(void)
{
     int  set[MAXSIZE];
     int  n, i;
     int  position;
     char line[100];

     printf("\nAll Possible Subsets Generation by Lexical Order");
     printf("\n================================================");
     printf("\n\nNumber of Elements in the Set --> ");
     gets(line);
     n = atoi(line);

     printf("\n{}");          /* the empty set            */
     position      = 0;       /* start from the 1st pos.  */
     set[position] = 1;       /* it gets a '1'            */
     while (LOOP) {           /* loop until done...       */
          printf("\n{%d", set[0]);  /* print one result   */
          for (i = 1; i <= position; i++)
               printf(",%d", set[i]);
          printf("}");

          if (set[position] < n) { /* this pos. can be inc*/
               set[position+1] = set[position] + 1; /* YES*/
               position++;    /* inc. next pos.           */
          }
          else if (position != 0)  /* NO, the 1st pos?    */
               set[--position]++;  /* backup and increase */
          else                /* NO, the 1st pos and can  */
               break;         /* not be inc. JOB DONE!    */
     }
}

【习题】

(1)有n个元素的集合的子集个数有2^n个，为什么前面所有的程序都不用一个for从 1数到2^n,而用break离开循环呢？（提示：想一想当n=50或100时会有什么后果）

(2)这个程序稍加改动就可以求出n个元素集合中元素个数不超过m(m<n)的所有子集，请把它写出来。

(3)这个程序也可以改成求出n个元素的集合中元素个数恰好是m(m<n)的所有子集，请把它写出来；请验查一下是否恰好有C(n，m)个？

注意：在编写（2)与（3)两题时，切不可以把所有子集都求出来，看看元素的个数，如果在所要的范围，就提出该集合。这样的写法是不能接受的，虽然正确；应该在编写本程序的概念上动动脑筋，只产生所要的集合，而不产生任何多余的部分才是正途。

(4)请写一个程序，把II个元素的集合的子集，用字典顺序的反顺序列出来（注意，不能保存各个子集)，然后用反顺序列出来，因为当n很大时内存就不够用了；试一试了解上面所讲的观点，直接把程序列出来。

问题 3.3 产生 Gray 码（GRAYCODE.C ）

编写一个程序，用Gray码（Gray Code)的顺序列出一个集合的所有子集。

【说明】

这个问题其实是在看有没有办法把Gray (人名）码用程序编写出来，有了Gray码，找出对应的集合是件简单的事，问题3.2己经讲过了。

什么是Gray码？ nbit的Gray码是一连串共有2^n个元素的数列，每一个元素都有nbit，而且任何相邻的两个元素之间只有1bit的值不同。例如，3个bit的Gray码：

000 001 011 010 110 111 101 100

是一组Gray码，任何相邻两个元素都只有1bit值不同。但是，Gray码却并不是惟一的，把它循环排列或是用反过来的顺序写，也会得到一组Gray码；比如说，如果把最后3个元素放到最前面去，就会得到：

111 101 100 000 001 011 010 110

也是一组Gray码。

Gray码是一个很直观的几何意义，不妨把nbit看成是n度空间中一个点的坐标，因此有2^n个坐标点，正好是n维空间中的一个正立方体的2^n个角落。如图3-1a所示，当n=2 时就是平方，是个正方形，如图3-1b所示，时就是个正立方体了。

如果能够从原点出发把每个顶点都走一次再回到原点，且每一个顶点都不重复，那么沿途经过的点的坐标，就是一个Gray码。在图3-1a中，依箭头顺序，会得到00，10，11，01;对图3-1b而言，则是000，001，011，010，110，111，101，100。当然，用不同的走法，就会有不同的Gray码。例如在图3-1b中，000,100,101,011,111,110,010就是一个很好的例子。

看看下面n=4的Gray码：

0000 0001 0011 0010

0110 0111 0101 0100

1100 1101 1111 1110

1010 1011 1001 1000

仔细看看哪一个位置是从0变到1的，它与左右两个邻居的关系如何，或许就有办法写成程序了。或者，如图3-1b所示，沿途经过的方向有何变化，也可以编写出程序。这只是两点提示，方法不止有这两个。

【解答】

把n=4的Gray码写出来：

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

如果位数是从右往左算，最右边一位是1，就会发现从第一个数到第二个数是第一位变了，第二个数到第三个数是第二位变了，把所有位置写下来有：

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

于是马上就可以归纳出：第奇数个的数（0000算是第0个）永远是改变上一个值最右边一位而得来的，可能是0变成1，也可能是1变成0;总之，变成了相反的值。

再看第偶数个的数（0011，0110，0101，1100，1111，1010，1001)，它们是从改变上一个值的2，3，2，4，2，3，2这几位而来；再仔细看看，它们的邻位（1，2，1，3，1，2，1)值都是1，而且是从右边算过来的第一个1。因此：第偶数个的数（0000不计）的值是从改变上一个值中右边算来第一个1的左边邻位而得来。

不过，程序并不打算用递归的写法，不用递归也并不困难，看看前述的那两条规则就行了。因为奇数位与偶数位是交错出现的，而且一开始最右边一位是第0位，也就是偶数位，所以可以用一个变量even,最先陚予其值为1，当处理完一位之后就把它改为1-even, 因为even的值就是1，0，1,0，…地变化；当值为1时，表示偶数位，值为0时是奇数位。如果目前是偶数位，就把最右边的位值改过来（0变成1, 1变成0);如果是奇数位，就从右向左找，找出第一个值为1的位，把它左边的那一位的值改变。做完之后，把修订过的结果显示出来。

为了程序编写方便，各个位的存放顺序，亦即digit[0]，digit[1]，…，digit[n-1]正好是第0 位（最左边），第1位,…，第n-1位（最左边)，所以在显示位的值时要用相反的顺序，且在取出对应的元素来显示时，顺序也是相反的，仔细看看显示Gray码与集合用的for循环就不难明白。程序的输出有两部分，左半是Gray码，右半是对应的集合。

【问题实现】

/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE         20
#define   YES             1
#define   LOOP            1

#define   FLIP_DIGIT(x)   x = ((x) == '0' ? '1' : '0')
#define   FLIP(x)         x = (1 - (x))

void main(void)
{
     char  digit[MAXSIZE];
     int   position[MAXSIZE];
     int   even;
     int   n;
     int   i, count = 0;
     char  line[100];

     printf("\nAll Subset Listing by Gray Code");
     printf("\n===============================");
     printf("\n\nNumber of Elements in Set Please --> ");
     gets(line);
     n = atoi(line);

     printf("\n");            /* initialization           */
     for (i = 0; i < n; i++) {
          digit[i] = '0';
          printf("0");
     }
     printf(" : {}\n");       /* the empty set            */

     even = YES;
     while (LOOP)  {
          if (even)           /* for even positions:0,2,..*/
               FLIP_DIGIT(digit[0]);  /* flip the 1st bit */
          else {              /* for odd positions...     */
               for (i = 0; i < n && digit[i] == '0'; i++)
                    ;         /* find the first 1 bit     */
               if (i == n-1) break; /* if it is the last..*/
               FLIP_DIGIT(digit[i+1]); /* NO, flip its nbr*/
          }
          for (count = 0, i = n - 1; i >= 0; i--) {
               printf("%c", digit[i]); /* print the bits  */
               if (digit[i] == '1')    /* and collect pos */
                    position[count++] = i + 1;
          }
          printf(" : {%d", position[count-1]);
          for (i = count - 2; i >= 0; i--) /* print pos   */
               printf(",%d", position[i]);
          printf("}\n");
          FLIP(even);         /* next will be odd(or even)*/
     }
}

【习题】

(1)记得河内之塔（Towers of Hanoi)这个游戏吗？有3个、4个与5个圆片，请用手算方式找出被搬动的圆片号码与Gray码有什么关联。请写一个程序，用Gray码来解河内之塔这个问题，这样就有了不用递归、没有堆栈的直接解法了。

(2)找一本书看看何谓中国九连环游戏（Chinese Ring Puzzle),把各个环的移动顺序与环的号码写下来，这一组号码与Gray码有什么关系。于是，又有了一个不用递归来解九连环游戏的解法。

(3)是否可以用递归的方法来写Gray码程序？会容易些吗？

问题3.4产生所有排列——旋转法(PERMUT_R.C）

编写一个程序，用旋转顺序（RotationOrder)列出n个元素的所有排列。

【说明】

旋转顺序并没有统一的定义，不过从下面4个元素的列法可以看出一点端倪。

在上面的例子中，4个元素经过上次旋转就会回到原来的样子，将前3个元素旋转一次（见上面加框的地方)，得到一个新的组合，这个组合旋转4次，又回到原样，因而再把前3个元素旋转一次；新组合旋转4次又还原，于是前3个元素再旋转一次，不过3个元素经过3次旋转之后又会还原，所以这3个元素的前两个元素还要旋转一次，一直到两个元

素的旋转也还原了，所有组合完全显现出来了。因为n个元素旋转n次就还原，所以就旋转前n-1个元素，这就产生了 n(n-1)个排列；但是前n-1个元素经过n-1旋转之后又会还原，因此又得旋转前n-2个元素，于是就有了n(n-1)(n-2)个排列。继续这样做，不就一共产生出n!个不同的排列了吗？

注意，要检查有没有还原成原样不必大动手脚，因为开始时是1234…n，所以只要n回到第n位，就表示这n个元素旋转了 n次；同理，n-1回到第n-1位，表示前n-1个元素旋转了 n-1次后还原；依此类推，当i回到第i位时，就是前i位被旋转了 i次后还原。但重要的是，这里是以大旋转来控制小旋转的，也就是说，n次n个元素的旋转之后，接着是一次n-1个元素的旋转；n-1次n-1个元素的旋转之后，接着是一次n-2个元素的旋转；......，i次i个元素的旋转之后，是一次i-1个元素的旋转。要如何把这个概念化成程序呢？请熟悉上面的例子，有可能的话，不妨试一试5个元素；所有的提示都讲过了，等全然明白以后，把程序编写出来。

【解答】

回想一下在问题说明中提过的n个元素的排列，如果从1，2，3，…，n起旋转，n次之后就会还原；换句话说，可以测试第n位，看它是否是n就知道还原了没有。如果还原了，旋转一次前n-1位，如果又还原了，就旋转前n-2位等；用p表示目前要旋转的是前p位，如程序12-4所示。

【程序】

程序12-4

while (还有位数可以旋转）{

p=第n位；

旋转1到第p位；

while (第p位等于p而且p至少是第二位）{

P--；

旋转1到第p位；

}

大循环是用来掌握整个n位的旋转的，所以在大循环里p就是第n位的位置；经过旋转之后到达内循环，在内循环中先看看第p位是不是p,如果是，就表示还原了，因为把p减去1,接着旋转时就是前p-i位了，再次旋转之后很可能又还原，因此p又向左移了一位，一直到p到达第一位为止，这时就无法左移，程序自然就结束了。不过，也有可能到某个p经过旋转之后并没有还原，于是又再度回到大循环，开始大旋转。

例如，如果在大循环中经过旋转后得到43125,因为第5位是5,所以大循环还原；进入内循环之后，就进行前4位的旋转，得到31245,不过第4位等于4,因此还不能离开内循环；下一次是前3个元素的旋转，得到12345;这一次第3位是3，仍然不能离开，因此开始前两位的旋转，得到21345。终于第2位不是2，于是离开内循环而进入大循环，因此大循环就会产生下一个排列，也就是52134，45213，34521，13452，21345;现在第5位还原，......。

程序PERMUT_R.C就是用这个方法写成的；注意，C语言的数组是从0算起的，因此第i位，脚码就是i-1,而不是i。程序中的变量position，就是上面的p,于是position值是0〜n-1之间。另外，为了方便，ROTATE是定成一个集体指令而非函数，当然写成函数亦无不可，但是在执行时间上却不一定快速。

【问题实现】

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE   20
#define   ROTATE(p) {  int  i, temp;              \
                       temp = perm[p];            \
                       for (i = p-1; i >= 0; i--) \
                            perm[i+1] = perm[i];  \
                       perm[0] = temp;            \
                    }

void main(void)
{
     int  perm[MAXSIZE];
     int  position;
     int  n;
     int  i;
     char line[100];

     printf("\nPermutation by Rotation Method");
     printf("\n==============================");
     printf("\n\nNumber of Elements --> ");
     gets(line);
     n = atoi(line);

     for (i = 0; i < n; i++)  /* initialize to 1,2,...,n  */
          perm[i] = i + 1;

     position = n - 1;           
     while (position != 0) {  /* if still have positions..*/
          printf("\n");       /* display result           */
          for (i = 0; i < n; i++)
               printf("%d ", perm[i]);

          position = n - 1;   /* starts from the last pos */
          ROTATE(position);   /* rotate them.             */
          while (perm[position]==position+1 && position!=0) {
               position--;    /* if last pos are equal and*/
               ROTATE(position); /* not zero, rotate again*/
          }
     }
}

【习题】

(1)有没有办法把这个旋转法写成递归程序？试试看。

(2)程序中，小旋转都是以左边第一位为基准的，如果要求把所有的旋转都放到右边去，程序要做什么样的改变？请把程序写出来。

(3)下面的方法是由GLangdon在1967年提出的，如程序12-5所示，请了解其操作方式，并且写成程序。

问题3.5产生所有排列——字典顺序（PERMU—LR C ）

编写一个程序，用字典顺序列出n个元素的所有排列（Permutation)。

【说明】

下面是一个n=4,用字典顺序列出来的所有排列，一共为4!=24个。

1234 2134 3124 4123

1243 2143 3142 4132

1324 2314 3214 4213

1342 2341 3241 4231

1423 2413 3412 4312

1432 2431 3421 4321

字典顺序的先后是这样定义的，如果a1a2…an与b1b2…bn是n个元素的两个排列，于是有 a1=b1，a2 =b2，…，ai =bi，但 ai+1<bi+1,就是说 a1a2 …an 在b1b2 …bn 的前面，或者说前者较“小”；注意自i+2个之后的各个元素是没有影响的。其实’这就是用来决定字符串大小的方式。举例而言，2314与2341,前两个元素相同，但第三个为1<4，所以 2314在前，2341在后；同理，1234与4321相比，1234在前，4321在后。

如何产生字典顺序的排列呢？据Hall与Knuth的考证，200年（1812年）前Fischer 与Kruse在他们的一本书中就己经提过这样的方法了。从123…n开始，首先从右到左找出第厂对满足ai<ai+1的ai与ai+1,于是从ai+1起在它右边的就是越来越小的；有了七之后, 再一次地从右到左查一次，找出第一个满足ai<aj的aj。接着把的各个元素k过来

排，就是字典顺序的下一个了。下面来看看如何找出153642的下一个：从右到左第一组满足ai<ai+1的是3与6,所ai就是3。接着从右到左去找第一个aj ,使得ai<aj则是4(3<4=；最后把3与4之间的元素反过来排，因此得到154632,这就是结果。

看另一个递归的做法，先看上面4!=24个排列的第一行，它们的第一个元素都是1,第一行最末一个是以1起头，用字典顺序排出来的最后一个，自然是1432。事实上，如果是n个元素的排列，应该会想到最后一个应该是1n(n-1)…432。下一行是2开头，把n(n-1）…432中最小的一个与1互换，得到2n(n-1)…431,但这绝对不是1n(n-1)…432的下一个，不过如果把后面的n-1个元素反过来排，就会得到2134…(n-1)n，还是正确的顺序，于是就进入第二行。第二行的最末应该是2n(n-1)-431,但1已经在第1行出现过了，所以把倒数第二个元素（自然是3)与2互换，得到3n(n-l)-421，再把后面的n-1个元素反过来排，有3124…(n-1)n是不是第三行的第一个呢？再做第三行，那是3n(n-l)…421，因为1与2已经在第一个位置出现过，这一次把4 换到头上去，得到4n(n-l)…321，再反过来排，就是4123…(n-1)n，正好是第四行。于是就可以归纳出一个递归的做法了，从1234…n起，用一个递归的程序：

(1) i = n 。

(2)排到n的排列（递归的）。

(3)把第i位与第一位互换。

(4)把后面的n-1位反过来排。

(5) i减去1。

(6)回到第（2)步。

请把这个想法发展成一个递归的程序。

【解答】

先讲递归的做法，n个元素一共有II!个排列，而1〜n都有可能出现在第一个位置，因为要用字符串顺序来排，所以这n!个排列是以1开头的(n-1)!个在前，接着是以2开始的 (n-1)!个，…，最后是以n开头的(n-1)!个。就用以i开头的为例，i已经在第1位，自第2 位起到第n位止中不会有i，因此以i开始的字典顺序以i 1 2 3…(i-1) (i+1)…（n-1) n 起，而以in (n-1)…(i+1) (i-1)…32 1结束。如果用递归方式，以字典顺序来排n-l个元素的程序，不过是把该(n-1)!排列（其中不含i)排出来，接在i的后面而已。

当以i起头的(n-1)!个排完后，如何产生以i+1起头，字典顺序的下一个呢？再套用上面的说法，这一组(n-1)!个排列以(i+1) 1 2 3…(i-1) i (i+2)…n起，到(i+1) n (n-1)···(i+2)i(i-1)…321止。可以把i起头的最后一个中的i+1 (它在倒数第i位）与i互换，因此得到：

(i+1k)n(n-l)…（i+2)i(i-1)…32 1

再把后面的n-1个元素反转：

(i+1) 1 2 3 …(i-1)i(i+2)…(n-1)n

这不就是(i+1)起头的第一个元素吗？

在写程序时要注意：因为要处理在后面的n-1个元素，所以用两个变量L与R来指出要处理的部分；如果用perrnu[]数组来存放一个排列的话，那么程序的架构就如程序12-7所示。

【程序】

程序12-7

while (1) {

排列perm [L+1]到permu [R]的部分;

把 perm [ L ]与 perm [ i ]互换；

把perm [L+1]到perm [R]反过来排；

i--;

}

当然，这还缺少递归的终止条件（以上面来看是永运不会停止的)；不过这很简单，当递归调用时，若L到R之间至少有3个元素，就做下去，而当只有两个元素时就不必递归调用了，此时接下来的两步正好就是两个元素的排列（两个元素的排列只有两种，一种是输入，另一种是两个元素互换——反过来排）。由此，递归韹序就可以写出来，这就是程序 PERMU—LR.C。

【问题实现】

#include <stdio.h>
#include <stdlib.h>

#define  LOOP         1
#define  SWAP(a,b)    { int t; t = a; a = b; b = t; }
#define  REVERSE(a,b) { int i, j;                            \
                        for (i=(a), j=(b); i < j; i++, j--)  \
                             SWAP(perm[i], perm[j]);         \
                      }
#define  DISPLAY(n)   { int i;                               \
                        printf("\n");                        \
                        for (i = 0; i < n; i++)              \
                             printf("%d ", perm[i]);         \
                      }
                        
void  again(int  perm[], int L, int R)
{
     int  i = R;

     while (LOOP) {
          if (R - L + 1 > 2) {
               again(perm, L+1, R);
               DISPLAY(R);
          }
          if (i > L ) {
               SWAP(perm[L], perm[i]);
               REVERSE(L+1, R);
               DISPLAY(R);
               i--;
          }
          else
               break;
     }
}


void permut(int perm[], int n)
{
     int  i;

     for (i = 0; i < n; i++)
          perm[i] = i + 1;
     again(perm, 0, n-1);
}


#define    MAXSIZE   20

void main(void)
{
     int   perm[MAXSIZE];
     char  line[100];
     int   n;

     gets(line);
     n = atoi(line);
     permut(perm, n);
}

【习题】

(1)在递归程序中R的值永远不变，因为它可以定成外部变量，因此wdls()函数的参数就变成只有一个L。请问R这个值是多少？接着请把程序的递归去掉，转换成非递归的程序。

(2)请证明Fischer-Kruse的方法是正确的；也就是说，如果己知一个排列，然后从右向左找出一个决满足ai<ai+1;再从右向左找出一个j,使得ai<aj（如果找不出来又如何？），接着把ai〜aj的元素反过来排，这就是给定排列在字典顺序中的下一个。

(3)本题的顺序是以字典顺序从小到大排的，请修改Fischer-Kruse以及递归程序，使它可以用反字典顺序排列。

(4)请把Fischer-Kruse方法写成非递归的形式。

问题3.6所有K个元素的子集（KSUBSET.C ）

编写一个程序，把一个n个元素的集合{1,2,3,•••,n}中所有k个元素的子集用字典顺序列出来。

【说明】

还记得列出所有子集的程序吗？问题3.2己经介绍了一个把所有子集用字典顺序列出来的例子，事实上，只要把那个例子的程序稍作修饰就可以做出这个问题的答案。

如果n=5,那么所有3个元素的子集用字典顺序来列就是

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

注意在每一个子集变到下一个子集时究竟是哪一个位置有所变动；另外，特别重要的是，每一个位置都有该位置的最大值。例如，第三位可以到5,第二位只能到4 (因为它到 5的话，第三位就不可能放3)，而第一位（最左边）则是3;这些最大值可以用n (总元素个数)、k (子集的个数）以及每一个元素的位置算出来。

了解这些想法之后，程序就很好写了，不妨自己动动脑筋。

【解答】

先列出{1，2，3，4，5}中3个元素的所有子集:

{1,2,3}

{1,2,4}

{1,2,5}

{1,3,4}

{1,3,5}

{1,4,5}

{2,3,4}

{2,3,5}

{2,4,5}

{3,4,5}

在幵始时是{1，2，3},接着会发现最右边的数逐渐增加，到n(=5)为止，然后它的左边位数进1，右边的位数则从下一个值开始；这个动作就像是一个里程表，各个位数不断增加, 所不同的是在例子中，从左向右的位数永远保持从小到大的位数。

正因为如此，只需要掌握在什么时候哪一位该进位就行了。能够产生出来的集合中最 “大”的一个{3，4，5},最后一位是最大元素，左边一位是5-1=4,再左一位是4-1(=5-2); 依次类推，如果原来的集合有n个元素，要取出的是k个元素的集合，那么最“大”的集合就是：

{n-k+1,···,n-2,n-1,n}

因此最后一位的值只能变到n，之后就退回一位，但右边第二位只能变到n-1,

如果仔细看看上面的例子，不难发现如下事实：

(1)如果最后一位的值小于n,那么再加1的位置永远是最后一位。

(2)如果从右边算来，每一位都等于它的最大值（最右边是n，右边第二位是n-1，…）, 那么再加1的位置是从右边往左边算，第一个小于极大值的位置。

以{2，3，4}为例，最右边一位(4)小于n=5，所以加1的位置是最后一位，因而得到{2，3，5};但倒数第二位却不是，所以倒数第二位加1，得到{2,4,5}，之后，第一位不到它的极大值，所以第一位加1，得到{3,4,5}，每一位都递归完，结束。

不过每次都要从右往左查是一件很麻烦的事，有没有别的办法直接定出要加1的是哪一位呢？很简单，不过又要进一步的思考而已，主要关键是第二点。做法是，使用一个变量（position)，它一开始时是k-1 (注意，C语言中的数组从零算起，而要求出k个元素的所有子集)，表示要加1的是第k位。在往后的工作中，如果第k位的值小于n, position 的值就维持在k-1,在这种情况下，被加1的永远是第k位。但是，若第k位的值已经到达了 n,就不能再加1 了，就把position减1,表示position左边那一位要加1。看起来有点奇怪，但是举个例子就不难明白。例如，n=5，k=3,现在有：

{1,3,4}

加了底线的地方就是position的位置，因为第k位小于n,自然position就在那，加了

1之后变成：

{1,3,5}

因此最后一位的值只能变到n，之后就退回一位，但右边第二位只能变到n-1,

【问题实现】

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE    20
#define   LOOP        1

void main(void)
{
     int  set[MAXSIZE];
     int  n;
     int  k;
     int  position;
     int  i, j;
     char line[100];

     printf("\nAll k Elements Subsets from a n Elements Set");
     printf("\n============================================");
     printf("\n\nNumber of Elements in the Set --> ");
     gets(line);
     n = atoi(line);
     printf("\n\nNumber of Elements in Subset ---> ");
     gets(line);
     k = atoi(line);

     for (i = 0; i < k; i++)  /* initialize the subset to */
          set[i] = i + 1;     /* {1,2,3,...,k}            */
     printf("\n{%d", set[0]); /* display it               */
     for (j = 1; j < k; j++)
          printf(",%d", set[j]);
     printf("}");


     position = k - 1;        /* 'position' indicates the */
     while (LOOP) {           /* pos to be increased      */
          if (set[k-1] == n)  /* if last pos is full, then*/
               position--;    /* move position left       */
          else                /* or if not full, then the */
               position = k - 1; /* pos is always the last*/
          set[position]++;    /* so add one to the pos.   */
          for (i = position+1; i < k; i++) /* add inc. all*/
               set[i] = set[i-1] + 1; /* pos to its right */

          printf("\n{%d", set[0]); /* display it.         */
          for (j = 1; j < k; j++)
               printf(",%d", set[j]);
          printf("}");

          if (set[0] >= n-k+1) break; /* if 1st pos full  */
     }
}

【习题】

(1)请用每一次都从左向右地找出position的值的方式（也就是解答中的两个事实）来改写程序。

(2)请写一个程序，把一个有n个元素的集合的所有子集依元素个数从小到大，而相同元素的子集用字典顺序排出来；以3个元素的集合来看，就是{}，{1}，{2}，{3}，{1，2}，{1，3}, {2，3}，{1,2，3}。

(3)如果a是一个有n个元素的集合的元素，请写一个程序，列出所有包含a,以及所有不包含a,并且元素个数都有k个的子集；请问，这各有多少个？这个数与n、k之间的关系如何？

问题3.7集合的所有分割方式（SETPART.C ）

一个集合S的分割（Partition）,就是把S分解成若千个子集S1，S2，…，Sp，（打不了下标，抱歉）使得S1∪S2∪…USp=S，但对任意两个不同的子集Si与Sj而言，Si∩Sj=∅，换句话说，集合

的分割，就是把该集合分解成若干相互分离的子集。举例而言，{1，2，3}的分割就有 {1},{2},{3}； {1,2},{3}； {1,3},{2}； {2，3}，{1}; {1，2，3}这 5 种。编写一个程序，读入 n，列出{1,2,3，…，n}的所有分割方式。

【说明】

一般而言，不会直接对{1,2,3，…，n}这个集合操作；聪明的做法是记录下哪一个元素在哪一个分割中，就以{1，2，3，4}为例，它的分割方式有下面的15种，如表3-2所示。

在上面的写法中，右边的四位数表示1，2，3，4在哪一个分割中。例如，1213表示1与3 在第一个分割，2在第二个，3在第三个，所以分割就是{1，3}，{2},{3}。再看1212,它指出 1与3在第一个分割，2与4在第二个分割，因此分割本身就是{1，3}，{2，4}。这个四位数就当作该分割的编码（Code)，只要能找出编码本身有什么性质，分割就可以从编码重建出来。

这个编码有一个特色，在分割中从{1，2，3，4}起，总是在第一个部分保持最长的分割，而把余下来的元素放到第二个分割中，接着就按这种形式把可能的方式都列出来，再把大的分割切成较小的部分，一直到不能再切割为止。更重要的是，永远把1所在的分割定成第一个，所以四位数中1这个元素的编码值永远是1。再看2这个元素，它的编码值永远不会大过2,为什么会这样呢？如果2在第三个分割中，就会有：

{1，…}••• {2，…}•••

因此中间分割中的元素值都大于3,但是可以把{2,…}这个部分换到前面而成为：

{1，…}{2，…}•••

因此2就在第二个分割中；这样做是正确的，因为分割本身并无次序性。推广开来，如果把分割中的元素从小到大排列，而且再把分割以第一个元素的顺序来排，那么i这个元素的编码一定小于或等于i。

不但如此，还可以证明：第i个元素的编码是小于或等于1，2，3，…，i-1这几个元素的编码的极大值再加上1。证明本身并不难，因为i在它所在的分割中，如果不是排在第一个（见 4个元素时的{3,4}),就是排在第一个后面（见4个元素时的{2，3}，或{2，3，4})。在前者，i 的编码如上述所讲的,最大就是i，不过|所在的分割最多只会排在{1,…}，{2,…}，…，{i-1,…} 后面，在这种情况下，1,2，…，i-1的编码 i 正好是1，2，…，i-1，只要其中有两个合二为一，1，2，…， i-1的编码值就会降低，所以i的编码值不能超过1，2，…，i-1的编码的极大值加上1。如果i 不是排在最前面，那么将i所在的分割中排在最前面的元素设为j，就一定小于或等于i-1。由上面的说明，i的编码值是1,2，…，j-1的编码的极大值加上1;更重要的是，在j+1到i-1 之间的元素一定落在1,2,…,j所在的分割之一，但因为i与j在同一个分割中，所以i也就是等于1到i-1的编码极大值再加上1 了。

用这个条件，就可以写一个很简单的程序了（建议是，把上面的说明彻底弄清楚之后再动手，不必忙着写程序)。

【问题实现】

#include <stdio.h>
#include <stdlib.h>           /* for malloc()             */

#define  ALWAYS   1

void  display(int *, int);

void  set_partition(int n)
{
     int  *code, *maxi;       /* arrays for code[], maxi[]*/
     int  i, j;

     code = (int *) malloc(sizeof(int)*n); /* get memory  */
     maxi = (int *) malloc(sizeof(int)*n);

     for (i = 0; i < n; i++)  /* initialization           */
          code[i] = 1, maxi[i] = 2;

     while (ALWAYS) {         /* loop until done.         */
          display(code, n);   /* display one partition    */
          for (i = n-1; code[i] == maxi[i]; i--)
               ;              /* find next 'increasible'  */
          if (i > 0) {        /* found ?                  */
               code[i]++;     /* YES, update              */
               for (j = i + 1; j < n; j++) {
                    code[j] = 1; 
                    maxi[j] = maxi[i]+((code[i]==maxi[i]) ? 1 : 0);
               }
          }
          else                /* NOT FOUND, done.         */
               break;
     }
     free(code);
     free(maxi);
}


/* ------------------------------------------------------ */
/* FUNCTION  display :                                    */
/*    This function displays the code of the partition.   */
/* ------------------------------------------------------ */

void  display(int *code, int n)
{
     int  i;
   
     printf("\n");
     for (i = 0; i < n; i++)
          printf("%3d", *(code+i));
}


/* ------------------------------------------------------ */

void main(void)
{
     char  line[100];
     int   n;

     printf("\nSet Partition Program for {1,2,3,...,N}");
     printf("\n=======================================");
     printf("\n\nN Please --> ");
     gets(line);
     n = atoi(line);
     printf("\nCodes of Partitions.");
     printf("\ni-th position = j means i in partition j\n");
     set_partition(n);
}

问题3.8整数的所有不同分割数目（INTPART#.C ）

所谓的整数的分割（Partition of an Integer)，指的就是把一个正整数写成若干个正整数的和，但这里只计较有多少种分解方式，而不计较它的内容。例如，4=3+1,2+2,2+1+1,1+1 +1+1,再加上自己，就一共有5种分割方式。编写一个程序，输入一个正整数，输出它有多少种分割方式。

【说明】

以下是几点重要的提示：

(1)要把n进行分割，其实不完全只针对n,还要看分割中最大的值是什么。例如，要把10进行分割，若在分割中最犬的值是6,亦即10=6+…，那么“…”的部分充其量的值是4而已，不仅如此，和还须等于4;因此，如果知道“…”，亦即4，有多少种分割方式，也正是在分割10时，最大值为6的分割方式！

(2)应该分析一下，n这个输入值，与在分割中的极大值（如（1)中的6)之间有什么联系，找出来，问题就解决了。

(3)不要忘了，递归是非常有效的武器。

【解答】

用p(n，m)表示在n的分割中极大值最多为m的分割数目，亦即分割具有n=m +…，n=m+m+…，n=m+m+m+…这一类的形式。于是n与m的关系不外子以下几种情况。

(1)m为1:因为n的分割中的极大值为1,而且分割中又完全是正整数，所以整个分割就都是1。以4为例，就是4=1+1+1+1。于是有p(n，1)=1。

(2) n为1:因为要分割的数本身就是1,这已经是正整数中最小的值了，所以不论如何分割，也不论m为何值，1 一定小于m, p(1,m)=l。

这两点就构成了递归调用的终止条件。在递归程序中，永远记住要找出能够令递归终止而返回结果或控制权的条件。

(1) n=m：也就是n的分割中，极大值不超过n的个数。当然，极大值为n的分割只有一个，也就是它自己。换言之，在4的分割中，4=4就是极大值正好是n的情況• 除 7这一个之后，极大值就不可能为n 了，最多是n-1而已。因此求出n的分割中极大值是 n-1的分割个数，再加上n=n这一个分割，就是p(n，n)。换句话说，p(n，n) = 1+ p(n，n-1)。

(2) n<m：要把n分割，但极大值最大可以为m,而且m〉n,这是不可能的事，因为把n分割时，在的情况下就已经是最大可能了。所以说，在n的分割中，如果要求极大倌最多可以到ni(>n),这是不切实际的，因为分割中不可能出现n+1，n+2，…这些值。

换言之，p(n，m) = p(m，n)。

(3) n>m：这是最常见的可能性了。在n的分割中，如果极大值最大可以为m,那么这不外乎分割中有一个或若干个m，或者是根本就没有m。比如，在4的分割中，说极大值最多可以到2，那么因为4=2+2=2+1+1=1+1+1+1，于是有m=2的就是2+2与2+1+1，完全没有m=2的则是1+1+1+1。如果n的分割中根本没有m，那么它的个数不就与n的分割中最大可以到m-1的个数（亦即p(n，m-1))相同吗？如果n的分割中至少有一个m，亦即n = m +…，（注意，…部分可能有m)，于是n-m=…，所以…的部分正好是n-m的一个分割，它的极大值最多可以到m;因为n-m的分割中极大值最多可以到m的有p(n-m，m) 个，再加上p(n，m-1)，这就是所有的情况，亦即p(n，m)=p(n，m-1)+p(n-m，m)。

这样就把所有的可能性都考虑到了。在程序中，compute()函数对应着p(n，m),变量 number是n，maximum则是m。它就依上述的5个情况分析，并且递归调用自己来求值。

那么n的分割数目是多少呢？是p(n，n)，这是说n的分割中极大值最多是n个数，自然地n的分割中不可能有大于n的情况。由上述的第(3)点，用compute(n，n)就可以得到结果了。但是，求n的分割只用到n—个参数而已，为什么要那么麻烦地写成computeOiji) 的两个呢？所以写一个额外的函数int_part_no()来做这件工作，把这件琐事处理掉(想想看，万一有一天在使用compute()时只给一个参数会有什么后果？）。

【问题实现】

unsigned long  compute(int, int);
unsigned long  int_part_no(int);

unsigned long  int_part_no(int n)
{
     return compute(n, n);    /* convert to another form */
}


unsigned long  compute(int number, int maximum)
{
     if (number == 1 || maximum == 1)
          return 1;
     else if (number < maximum)
          return compute(number, number);
     else if (number == maximum)
          return 1 + compute(number, maximum-1);
     else
          return compute(number,maximum-1) + 
                 compute(number-maximum,maximum);
}

/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>

void  main(void)
{
     int  n;
     char line[100];

     printf("\nNumber of partitions of an Integer");
     printf("\n==================================");
     printf("\n\nN --> ");
     gets(line);
     n = atoi(line);
     printf("\nThere are %lu partitions.", int_part_no(n));
}

【习题】

(1)请把这个程序改写成非递归的形式。

提示：可以用一个表格来做这件事，如table[n][m]，就存放了 p(n，m)的值，这个表格的计算次序如何?

(2)一个集合的分割，就是把该集合分解成若干个两两分离的非空集合，并且这些子集的合集等于已知的集合。例如，{3，2，1}的分割有{1}，{2}，{3}; {1},{2,3}； {1,2},{3}； {1,3},{2}； {1,2,3}这3种.请写一个程序，读入集合的元素个数，输出这个集合会有多少种不同的分割方式，这个数叫做Bell数。

提示：与例题一样，此处的集合分割中，分解成几个部分的数目是非常重要的，囚此分解成1个，2个，…，到n个（假设集合有n个元素）部分的不同做法都知道了，加起来就是所有的分割方式，想法与此处的程序大同小异。

(3)请问在程序中一共用了多少个加法，递归调用了多少次？为了要算p(n，m)，有必要求出所有p(i,j)的值吗？此地1<=i<=n,1<=j<=n。

(4)用G(n)表示在有n位的二进制数中没有相邻的两个1的二进制数个数。比如，当 n=3 时，000,001,010,011,100,101,110,111 这 8 个数中只有 000,001,010,100,101 这 5 个是没有相邻为1的，故G⑶=5。请写一个程序，输入n,输出G(n)的值。

提示:不应该000…000〜111…111 一个个地测试，请试一试“分而治之”的策略，把n位二进制数分成两部分，分别处理这两部分，并且小心地合并。

问题3.9整数的分割方式（INTPART.C ）

对于一个正整数n而言，它的一个分割（Partition),就是把n写成若干个正整数的和, 但不计较书写的顺序。编写一个程序，输入n，把n的所有分割显示出来。

【说明】

如果n=7,那么有如下的分割。

一共有12个，仔细观察在各个输出中前后两者的差异,并且自己做一做其他的结果（比如n-5时有7个，n=6时有11个等)，就不难写出程序了。

【解答】

把正整数分割成若干正整数的和并不是一个十分困难的问题。如果回头看问题说明中把7分解的例子，就不难发现从上一个分割方式到下一个分割式中，永远是最右边或是旁边的一连串1的位数有所改变。其实在问题说明中的排列方式，正是所谓的反字符串顺序，就以4、3为例，它的下一个是多少？因为最右边位数的3还有可以分解的余地，但比3小的下一个分解是2，3就分解成2+1，故7=4+3=4+2+1;到了 4+2+1之后，1自然不能分解了，但1左边的2还可以，所以把2分解成1+1，故得到7=4+1+1+1。接着，下一个可以再度分解的是4,4可以分解成3，因此7=3+x，后面的x是多少呢？自然它们的和是7-3=4，但此地不能用4,因为在此之前己经用过了，而用比3小的才行，要比3小，那只有2, 7=3+2+2,于是接下来的是7=3+2+1+1，…。这就是解题的基本想法。

不过为了要把题目解得漂亮，要有进一步的、好的数据结构才行。为什么呢？因为在分解成正整数的和时，可能会有很多重复的部分，特别是要分解的数很大时就更是如此。 10=4+3+3=3+2+2+2+1=…就是一个例子，因此用两个数组来做这件事。partition□中储存了分解出来的、不同的正整数，而1111111[]则用来记录对应的整数的重复次数；以 10=3+2+2+1+1+1 为例，partition[]中依次为 3、2、1,而 mult[]中则是 1、2、3,因为 3 有 1次，2有两次，而1有3次，为了说明方便起见，不用partition[0]与mult[0]。

在开始时，如果要分解的数是n，那么partitionfl]就是n,而mult[1]为1,表示只出现一次，接下来就要把上面所讲的观点转化成程序了。用part_no记录下n在目前一共分解成多少个不同的整数，依照上面的说法，可以分成两个部分来说：

(1)最后一个值不是1:就以25=5+4+4+3+3+3+3为例，partition[]依次为5，4，3,而 mult[]则是1,2，4;因为最后一个数(3)不是1,所以可以把它分离出来，减去1就是下一个数（2=3-1):

25=5+4+4+3+3+3+(2+···)

但因为分离出来的是3，它的下一个较小的值是2,那么有多少个2呢？很简单，3/2=1 个2,所以partition[]变成5，4，3，2，mult[]则是1，2，3，1;但是3不能被2整除，还有剩余的数（也就是商数，它必定小于2),所以就加在最后面，因此得到：

25=5+4+4+3+3+3+2+1

总而言之，如果partition[part_no],也就是最后一个数值不为1,就可以把它取一个出来，叫做sum,表示取出之后必须要加上sum的值才能得到和为n。其次，下一个数要比

partition[part_noj小，亦即值为partition[part_no]-1,把这个值存到size中；这代表在分割中的下一个值。但是要注意一点，当mult[part_no]为1时，取出这个值之后原来的数就没有

了（例如，在16=5+4+4+3中取了 3之后，3这个部分就不存在了），所以当mult[part_no] 不是1时，可以多一个数；但当mult[part_n0]为1时，则不能多一个数。

因为size代表下一个值，所以把它存到part_no所指出的下一个位置中，它能够重复多少次呢？前面说过，sum/size次；但若size不能整除sum,多出来的余数部分就是一个新的值。例如，对25而言，如果partition[]中是5，4，3，mult[]为1，2，4;于是sum为3，表示从最后的4个3中取了一个3出来，size是2,因为比3小的下一个值是2。由于取了一个 3，故mult[]的新值为1，2，3，多出来的这个sum可以被size分成3/2=1组，所以partitionf ] 为5，4，3，2，mult[]则是1，2，3，1;不过正因为sum不能被size整除，还余1,所以这个1就形成一个新的部分，把它加到分割中，有partition□为5，4，3，2，1, muh[]为1，2,3，1，1。但若 25=11+11+3, partition□为 11，3，mult[]Sl;因此 sum=3, size 是 2;但因为 3 被取出之后，

在原来分割中就不存在了，所以新产生的分割（sum/size)就像它原来的位置，即结果中 partition[]为 11，11，2，1，mult[]是 2，1，1。

(2)如果最后一个值是1:这些1 一定在最后面，也就是partition [part_ no]，有多少个则是在mult[part_no]中，因为mult[part_no]指出有多少个1,因此也正是由1所构成的部分的总和。因为1已经不能再分解了，所以在求下一个分解方式时，这些1都要去掉，而下一个值是从最后的一个不是1的值中取一个出来，再减去1;于是sum就是 mult[part_no]+1，而 size 则是 partition [part_no-1]-1;为什么 sum 是 mult[part_no]+1,而不是mult[part_no]呢？原因是，sum是加上的值而凑成n用的，因为下一个可以用的值是 partition[part_no-1]-1,少了 1,所以就要在sum中多加一个1来弥补了。例如 14=4+3+3+1+1+1+1, partition[]是 4，3，1，mult[]为 1，2，4,自然 sum 为 4，但因为最后一个不是1而为2，所以取出来又少了 1，因此在sum中加上1变成1作弥补：

14 = 4 + 3 + 3 + 1 + 1 + 1 + 1 =4 + 3 + 3 + (4)

=4 + 3 + (2 + 1) + (4)

=4 + 3 + 2 + (5)

于是sum是5, size为2，其他工作就与上一点相同了，从sum/size求出sum可以用 size分成多少组，加上从上一个值中取出的一组，就一共有sum/size+1。于是新的partition[] 是 4，3，2，1, mult[]为 1，1，3，1。

程序INTPART.C是完全按照上面的观点写成的,只不过是上面求sum与size的工作合二为一而已，所以不应该会有任何困难。为了彻底地了解这个方法，建议找一个比较大的数（比如8),从头开始用手算几个结果，就不难熟悉整个的处理过程。

【问题实现】

//* ------------------------------------------------------ */
/* PROGRAM  integer partition :                           */
/*    Given a positive integer n, this program lists all  */
/* partition of n in anti-lexical order.                  */
/*                                                        */
/* Copyright Ching-Kuang Shene               July/21/1989 */
/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>          /* for atoi()               */

#define   MAXSIZE   20

void  display(int [], int [], int);

void  main(void)
{
     int  partition[MAXSIZE+1]; /* the actuall partition  */
     int  mult[MAXSIZE+1];      /* multiplicity           */
     int  part_no;              /* no. of parts           */
     int  sum, size, remainder, count;
     int  n;
     char line[100];

     printf("\nPartition of Integer");
     printf("\n====================");
     printf("\n\nInput a Positive Integer --> ");
     gets(line);
     n = atoi(line);

     partition[1] = n;        /* at the biginning, we have*/
     mult[1]      = part_no = count = 1; /* only one part.*/
     display(partition, mult, part_no);

     do {                     /* size one sum in 'sum'    */
          sum  = (partition[part_no]==1) ? mult[part_no--]+1 : 1;
          size = partition[part_no] - 1; /* dec. size     */
          if (mult[part_no] != 1)  /* last part with mul=1*/
               mult[part_no++]--;  /* NO, cut this part   */
          partition[part_no] = size; /* set new part=size */
          mult[part_no]      = sum/size + 1; /* fill other*/
          if ((remainder = sum % size) != 0) {
               partition[++part_no] = remainder;
               mult[part_no]        = 1;
          }
          count++;
          display(partition, mult, part_no);
     } while (mult[part_no] != n);
     printf("\n\nThere are %d partitions in anti-lexical order",
             count);
}


/* ------------------------------------------------------ */
/* FUNCTION display :                                     */
/*    This routine displays the given partition.          */
/* ------------------------------------------------------ */

void  display(int partition[], int mult[], int part_no)
{
     int  i, j;

     printf("\n");
     for (i = 1; i <= part_no; i++)      /* for each part */
          for (j = 1; j <= mult[i]; j++) /* and its mult. */
               printf("%3d", partition[i]); /* show them  */
}

【习题】

此处所列的是反字典顺序，能否修改这个程序用字典顺序列出结果呢？换言之，把5 用 1+1+1+1+1，2+1+1+1，2+2+1，3+1+1，3+2，4+1 这 6 个顺序列出来。

参考：

C语言明天精选百则冼镜光著