1. Fw: enumerating all the combinations
- Posted by ck lester <cklester at YAHOO.COM> Sep 10, 2000
- 344 views
Can anybody decode this into EUPHORIA? > #include <malloc.h> > #include <stdio.h> > #include <assert.h> > > int** binom; /* after initialization, binom[i][j] is (i+j)!/i!j! */ > > static int** binomInit(int size) > { > int i; > int** binom = 1 + (int**) malloc((size+1) * sizeof(int*)); > binom[-1] = 1 + (int*) malloc((size+1) * (size+1) * sizeof(int)); > binom[0] = binom[-1] + size + 1; > binom[-1][-1] = binom[-1][0] = binom[0][-1] = 0; > binom[0][0] = 1; > for (i = 1; i < size; ++i) > { > int j, t; > binom[i] = binom[i-1] + size + 1; > binom[i][-1] = binom[-1][i] = > t = 0; > for (j = 0; j <= i; ++j) > binom[i][j] = binom[j][i] = > t += binom[i-1][j]; > } > return binom; > } > > #define insertElt(array, t) ((array) |= (1<<(t))) > #define removeElt(array, t) ((array) &= ~(1<<(t))) > #define containsElt(array, t) (((array) >> (t)) & 1) > > int comb_to_int(int s, int u, unsigned long element) > { > int answer = 0; > while (--s) > { > answer += binom[u-s][s]; > while ((element & 1) == 0) > { > element >>= 1; > --u; > } > answer -= binom[u-s][s]; > element >>= 1; > --u; > } > return answer; > } > > unsigned long int_to_comb(int s, int u, int i) > { > unsigned long element = 0; > int k = 0; > while (s > 0) > { > if (i < binom[u-s][s-1]) > { > insertElt(element, k); > --s; > } > else > i -= binom[u-s][s-1]; > ++k; > --u; > } > assert(i == 0); > return element; > } > > void print_elements(unsigned long array) > { > unsigned t; > for (t = 0; array!=0; ++t) > { > if (containsElt(array, t)) > printf(" %d", t); > removeElt(array, t); > } > printf("\n"); > } > > int main() > { > int u,s; > unsigned long array; > printf("Enter maximum universe size and maximum set size: \n"); > scanf("%d%d", &u, &s); > binom = binomInit(1+u); > > for (;;) > { > char c; > int i; > getchar(); > printf("'i', 'c', 'e', 'u', 's', 'q', or '?' (help): \n"); > c = getchar(); > switch(c) > { > case 'i': > { > printf("Enter %d items from 0 to %d: \n", s, u-1); > array = 0; > for (i = 0; i < s; ++i) > { > int t; > scanf("%d", &t); > insertElt(array, t); > } > i = comb_to_int(s,u,array); > printf("Index is %d\n", i); > } break; > case 'c': > { > int t; > printf("Enter an index: \n", i); > scanf("%d", &i); > array = int_to_comb(s, u, i); > printf("The corresponding combination is: \n"); > print_elements(array); > } break; > case 'e': > { > printf("An enumeration of all combinations:\n"); > /*for (i = 0; i < binom[s][u-s]; ++i)*/ > for (i = 0; i < binom[s][u-s]; ++i ) > { > printf("%4d: ", i); > print_elements(int_to_comb(s, u, i)); > } > break; > } > case 'u': > { > printf("Enter a new value for the number of distinct elements: \n", i); > scanf("%d", &u); > } break; > case 's': > { > printf("Enter a new value for the set size: \n", i); > scanf("%d", &s); > } break; > case 'q': > return 0; > case '?': > { > printf("Type 'i' to convert a combination to an index.\n"); > printf("Type 'c' to convert an index to a combination.\n"); > printf("Type 'e' to enumerate the combinations.\n"); > printf("Type 'u' to change the size of the universe of items.\n"); > printf("Type 's' to change the size of the sets of items.\n"); > printf("Type 'q' to quit.\n"); > printf("Type '?' to get this explanation.\n"); > } break; > default: > break; > } > } > } > > > For some fortran see: > http://ftp.cac.psu.edu/pub/ger/fortran/hdk/ > > For Code Snippets: > http://remus.rutgers.edu/~rhoads/Code/code.html > > For more info: > http://www.caam.rice.edu/~dougm/twiddle/EnumComb.html > http://www.caam.rice.edu/~dougm/twiddle/ _________________________________________________________ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com