/* distribute -- put P copies of N things in M buckets without duplicates * * This can be used, e.g. to assign papers to a committee of * reviewers: There are N papers, M reviewers, each paper must be * reviewed by P reviewers. And we want all reviewers review (about) * the same number of papers. * * Obviously P <= M and M > 0. (P = 0 or N = 0 is allowed, but not * very interesting.) * * To do: scanf() doesn't detect overflow. * * Copyright © 2014 World Wide Web Consortium * See http://www.w3.org/Consortium/Legal/2002/copyright-software-20021231 * * Author: bert Bos * Created: 24 jan 2014 */ #include #include #include #include #include /* random_uniform -- return random number in range 0..(n-1) */ static int random_uniform(int n) { int r, m = RAND_MAX - (RAND_MAX % n); do {r = random();} while (r >= m); /* Avoid "modulo bias" */ return r % n; } int main(int argc, char *argv[]) { int nitems, nbuckets, ncopies, i, j, maxitems, k, p, q; static int **bucket; /* Read three numbers from stdin or from the command line arguments */ if (argc == 1) { if (isatty(0)) printf("Number of items: "); if (scanf(" %i", &nitems) < 1) errx(1, "Expected a number"); if (isatty(0)) printf("Number of buckets: "); if (scanf(" %i", &nbuckets) < 1) errx(1, "Expected a number"); if (isatty(0)) printf("Number of copies: "); if (scanf(" %i", &ncopies) < 1) errx(1, "Expected a number"); } else if (argc == 4) { if (sscanf(argv[1]," %u",&nitems)<1) errx(1," must be a number"); if (sscanf(argv[2]," %u",&nbuckets)<1) errx(1," must be a number"); if (sscanf(argv[3]," %u",&ncopies)<1) errx(1," must be a number"); } else { fprintf(stderr, "Usage: %s [items buckets copies]\n", argv[0]); exit(1); } if (nitems < 0) errx(1, " is too big or too small"); if (nbuckets <= 0) errx(1, " is too big or too small"); if (ncopies < 0) errx(1, " is too big or too small"); if (ncopies > nbuckets) errx(1, " cannot be greater than "); /* Each bucket will get maxitems or (maxitems - 1) items */ maxitems = (nitems * ncopies + nbuckets - 1) / nbuckets; /* Allocate an array of buckets */ bucket = malloc(nbuckets * sizeof(*bucket)); if (!bucket) err(1, NULL); for (i = 0; i < nbuckets; i++) { bucket[i] = malloc(maxitems * sizeof(**bucket)); if (!bucket[i]) err(1, NULL); } /* Place maxitems * nbuckets items (which may be a few too many) */ srandom(time(NULL)); p = 1; /* Item to place */ q = 0; /* Copies of item p already placed */ for (j = 0; j < maxitems; j++) { for (i = 0; i < nbuckets; i++) { k = random_uniform(nbuckets - i); /* Choose a bucket */ bucket[k][j] = p; /* Put p in that bucket */ /* Move the bucket to the end of the list */ int *h = bucket[k]; bucket[k] = bucket[nbuckets-1-i]; bucket[nbuckets-1-i] = h; /* If p has been placed ncopies times, go to next p */ if (++q == ncopies) {p++; q = 0;} } } /* Print result (omitting the items that were too many) */ for (i = 0; i < nbuckets; i++) { printf("Bucket %u:", i + 1); /* Number them 1,2... instead of 0,1... */ for (j = 0; j < maxitems; j++) if (bucket[i][j] <= nitems) printf(" %u", bucket[i][j]); printf("\n"); } return 0; }