01: #include<stdio.h>
02: #include<stdlib.h>
03: #include<math.h>
04: 
05: unsigned int bit(unsigned long, unsigned int, unsigned int);
06: int h(unsigned long, unsigned int, unsigned int);
07: 
08: int main(int argc, char **argv){
09: 
10:   unsigned int n2;
11:   do
12:   {
13:     printf("Inserisci un numero di bit da analizzare (pari): ");
14:     scanf("%u", &n2);
15:   }
16:   while(n2%2); // repeat until we have an even number
17: 
18:   unsigned long max = pow(2, n2-1) - 1; // max unsigned integer we can store in n2-1 bits (first bit must always be 0)
19: 
20:   int totparole = 0;
21:   for(unsigned long x = 0; x <= max; ++x) // check all numbers
22:   {
23:     // first I check whether we have the same number of 1 and 0 in the binary representation of x
24:     if(h(x, n2, n2)) 
25:       continue;
26: 
27:     // than I check that for all substrings of the binary representation the evaluation function is always >=0
28:     int i;
29:     for(i = 1; i <= n2-1; ++i)
30:       if(h(x, i, n2) < 0)
31:   break;
32: 
33:     if(i != n2) // true when the break was issued
34:       continue;
35: 
36:     ++totparole; // if we are here, we found a Dyck word
37:     printf("%10lu: ", x);
38:     for(int b=1; b<=n2; ++b)
39:       printf("%u", bit(x, b, n2));
40:     printf("\n");
41:   }
42:   printf("Il numero totale di parole di Dyck trovate e' %d\n", totparole);
43: 
44:   return 0;
45: }
46: 
47: unsigned int bit(unsigned long x, unsigned int i, unsigned int nbits)
48: {
49:   if(i < 1 || i > nbits)
50:   {
51:     printf("ERROR: invoked bit() with i=%d on %d\n", i, nbits);
52:     printf("\n");
53:   }
54: 
55:   return (x>>(nbits-i))&1;
56: }
57: 
58: // recursive implementation for h()
59: int h(unsigned long x, unsigned int i, unsigned int nbits)
60: {
61:   if(!i)
62:     return 0;
63:   if(bit(x, i, nbits) == 1)
64:     return h(x, i-1, nbits) - 1;
65:   else
66:     return h(x, i-1, nbits) + 1;
67:   // a shorter version for the selection:   return (bit(x, i, nbits) == 1) ? h(x, i-1, nbits) - 1 : h(x, i-1, nbits) + 1;
68: }
69: 
70: /* NON RECURSIVE IMPLEMENTATION FOR h()
71:    int h(unsigned long x, unsigned int i, unsigned int nbits)
72:    {
73:    int tot = 0;
74:    for(int b = 1; b <= i; ++b)
75:    if(bit(x, b, nbits) == 1)
76:    --tot;
77:    else
78:    ++tot;
79:    return tot;
80:    }
81: 
82:  */
83: