/* ------------------------------------------------------ */
/* 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  */
}


评论