#include /* printp - print out the partitioning scheme s of n elements as: {1, 2, 4} {3} */ void printp(int *s, int n) { /* Get the total number of partitions. In the exemple above, 2.*/ int part_num = 1; int i; for (i = 0; i < n; ++i) if (s[i] > part_num) part_num = s[i]; /* Print the p partitions. */ int p; for (p = part_num; p >= 1; --p) { printf("{"); /* If s[i] == p, then i + 1 is part of the pth partition. */ for (i = 0; i < n; ++i) if (s[i] == p) printf("%d, ", i + 1); printf("\b\b} "); } printf("\n"); } /* next - given the partitioning scheme represented by s and m, generate the next Returns: 1, if a valid partitioning was found 0, otherwise */ int next(int *s, int *m, int n) { /* Update s: 1 1 1 1 -> 2 1 1 1 -> 1 2 1 1 -> 2 2 1 1 -> 3 2 1 1 -> 1 1 2 1 ... */ /*int j; printf(" -> ("); for (j = 0; j < n; ++j) printf("%d, ", s[j]); printf("\b\b)\n");*/ int i = 0; ++s[i]; while ((i < n - 1) && (s[i] > m[i] + 1)) { s[i] = 1; ++i; ++s[i]; } /* If i is has reached n-1 th element, then the last unique partitiong has been found*/ if (i == n - 1) return 0; /* Because all the first i elements are now 1, s[i] (i + 1 th element) is the largest. So we update max by copying it to all the first i positions in m.*/ int max = s[i]; for (i = i - 1; i >= 0; --i) m[i] = max; /* for (i = 0; i < n; ++i) printf("%d ", m[i]); getchar();*/ return 1; } int main(int argc, char *argv[]) { int s[16]; /* s[i] is the number of the set in which the ith element should go */ int m[16]; /* m[i] is the largest of the first i elements in s*/ int n = 3; int i; /* The first way to partition a set is to put all the elements in the same subset. */ for (i = 0; i < n; ++i) { s[i] = 1; m[i] = 1; } /* Print the first partitioning. */ printp(s, n); /* Print the other partitioning schemes. */ while (next(s, m, n)) printp(s, n); return 0; }