#include <stdio.h> #include <stdlib.h> /* For exit() */ /* Based on an algorithm from Brian Wickman to generate unique racks. #define DBMAIN to get the stand-alone version complete with main(). Heavily modified to make it a producer and non-recursive. Uses manually-programmed co-routine structure. Does 2 iterations in 2.9s on a 2.5GHz Dell */ static char *nextdraw(int drawsize, char *rack) { #define RUNNING 0 #define COBREAK 1 #define push(i) stack[stackp++] = i #define pop(i) i = stack[--stackp] static int tot[256]; static int rackcount[256]; static int FIRSTTILE = 0; /* defaults work, but narrow these for speed */ static int LASTTILE = 256; /* The closer the blank is to the letters (eg 'A'-1), the better */ static int stackp = 0; static char buffer[8]; // Max rack size + 1 static int state=RUNNING; static int stack[(256+COBREAK)*3]; /* Alphabet size * 3 */ int i, tile, sum, nexttile, nextsum; if (state == COBREAK) goto RESUME; // resume co-routine // otherwise initial entry point. Set everything up here. for (i = 0; i < 256; i++) {rackcount[i] = 0;tot[i] = 0;} {char *s = rack; while (*s != '\0') tot[*s++]++;} LASTTILE = 256; while (tot[--LASTTILE] == 0); ++LASTTILE; FIRSTTILE = 0; while (tot[FIRSTTILE++] == 0); --FIRSTTILE; stackp = 0; tile = FIRSTTILE; sum = 0; RECURSE: i = ((tot[tile] >= drawsize) ? drawsize : tot[tile])+1; NEXT: if (--i < 0) goto BREAK; rackcount[tile] = i; /* Because there may be gaps in the alphabet */ /* (and also the blank is off to one side) */ nexttile = tile; while ((++nexttile < LASTTILE) && (tot[nexttile] == 0)); if ((nexttile <= LASTTILE) && ((nextsum = sum + i) <= drawsize)) { if (nextsum == drawsize) { int k, j; char *p = buffer; for (k = FIRSTTILE; k < LASTTILE; k++) if (rackcount[k] > 0) for (j = 0; j < rackcount[k]; j++) *p++ = k; *p = 0; push(tile); push(sum); push(i); state=COBREAK; return(buffer); RESUME: state=RUNNING; } else { push(tile); push(sum); push(i); tile = nexttile; sum = nextsum; goto RECURSE; RETURN:; } pop(i); pop(sum); pop(tile); } goto NEXT; BREAK: rackcount[tile] = 0; if (stackp != 0) goto RETURN; return(NULL); /* DONE */ } #ifdef DBMAIN #define FULLRACK "aaaaaaaaabbccddddeeeeeeeeeeeeffggghhiiiiiiiiijkllllmm\ nnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz??" int main(void) { int i, j; for (j = 0; j < 2; j++) { // We do it twice to test the termination/reset i = 0; for (;;) { char *s = nextdraw(7, FULLRACK); if (s == NULL) break; if ((i < 3) || (i > 3199720)) fprintf(stdout, "%d: %s\n", i, s); i += 1; } if (i != 3199724) fprintf(stderr, "The last item was #%d - should have been 3199724\n", i); } exit(0); return(0); } #endif