1. Fw: enumerating all the combinations
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
