combi.c

   1 #include <assert.h>
   2 #include <string.h>
   3
   4 #include "puzzles.h"
   5
   6 /* horrific and doesn't check overflow. */
   7 static long factx(long x, long y)
   8 {
   9     long acc = 1, i;
  10
  11     for (i = y; i <= x; i++)
  12         acc *= i;
  13     return acc;
  14 }
  15
  16 void reset_combi(combi_ctx *combi)
  17 {
  18     int i;
  19     combi->nleft = combi->total;
  20     for (i = 0; i < combi->r; i++)
  21         combi->a[i] = i;
  22 }
  23
  24 combi_ctx *new_combi(int r, int n)
  25 {
  26     long nfr, nrf;
  27     combi_ctx *combi;
  28
  29     assert(r <= n);
  30     assert(n >= 1);
  31
  32     combi = snew(combi_ctx);
  33     memset(combi, 0, sizeof(combi_ctx));
  34     combi->r = r;
  35     combi->n = n;
  36
  37     combi->a = snewn(r, int);
  38     memset(combi->a, 0, r * sizeof(int));
  39
  40     nfr = factx(n, r+1);
  41     nrf = factx(n-r, 1);
  42     combi->total = (int)(nfr / nrf);
  43
  44     reset_combi(combi);
  45     return combi;
  46 }
  47
  48 /* returns NULL when we're done otherwise returns input. */
  49 combi_ctx *next_combi(combi_ctx *combi)
  50 {
  51     int i = combi->r - 1, j;
  52
  53     if (combi->nleft == combi->total)
  54         goto done;
  55     else if (combi->nleft <= 0)
  56         return NULL;
  57
  58     while (combi->a[i] == combi->n - combi->r + i)
  59         i--;
  60     combi->a[i] += 1;
  61     for (j = i+1; j < combi->r; j++)
  62         combi->a[j] = combi->a[i] + j - i;
  63
  64     done:
  65     combi->nleft--;
  66     return combi;
  67 }
  68
  69 void free_combi(combi_ctx *combi)
  70 {
  71     sfree(combi->a);
  72     sfree(combi);
  73 }
  74
  75 /* compile this with:
  76  *   gcc -o combi.exe -DSTANDALONE_COMBI_TEST combi.c malloc.c
  77  */
  78 #ifdef STANDALONE_COMBI_TEST
  79
  80 #include <stdio.h>
  81
  82 void fatal(char *fmt, ...)
  83 {
  84     abort();
  85 }
  86
  87 int main(int argc, char *argv[])
  88 {
  89     combi_ctx *c;
  90     int i, r, n;
  91
  92     if (argc < 3) {
  93         fprintf(stderr, "Usage: combi R N\n");
  94         exit(1);
  95     }
  96
  97     r = atoi(argv[1]); n = atoi(argv[2]);
  98     c = new_combi(r, n);
  99     printf("combi %d of %d, %d elements.\n", c->r, c->n, c->total);
 100
 101     while (next_combi(c)) {
 102         for (i = 0; i < c->r; i++) {
 103             printf("%d ", c->a[i]);
 104         }
 105         printf("\n");
 106     }
 107     free_combi(c);
 108 }
 109
 110 #endif