#include "stdio.h" typedef unsigned char BYTE; typedef unsigned long int ULI; typedef unsigned long long int ULLI; typedef long long int SLLI; typedef ULLI TBBS; /* TBBS = totally balanced binary sequence. */ typedef ULI RANK; /* With 32 bit we can go upto n=19 with 64 much further. */ typedef int SIZE; /* Pointer to function that accepts a TBBS and returns TBBS (for gatomorphisms that work directly on TBBS'es, not S-expressions). */ typedef TBBS (*PFGATOTBBS)(TBBS); int glob_opt_out_cycle_lists = 1; RANK sA00108[20] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, /* The last value < 2^32 */ /* 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198 */ }; #define Cat(n) (sA00108[n]) /* Note: both rows and columns start from -1 */ /* Entry at CatTriangle(r,m) = CatTriangle(r,m-1) + CatTriangle(r-1,m) */ #define CatTriangle(r,c) (tA009766[(r+1)][(c+1)]) RANK tA009766[][21] = /* 34 in full. */ { {0}, {0, 1}, {0, 1, 1}, {0, 1, 2, 2}, {0, 1, 3, 5, 5}, {0, 1, 4, 9, 14, 14}, {0, 1, 5, 14, 28, 42, 42}, {0, 1, 6, 20, 48, 90, 132, 132}, {0, 1, 7, 27, 75, 165, 297, 429, 429}, {0, 1, 8, 35, 110, 275, 572, 1001, 1430, 1430}, {0, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 4862}, {0, 1, 10, 54, 208, 637, 1638, 3640, 7072, 11934, 16796, 16796}, {0, 1, 11, 65, 273, 910, 2548, 6188, 13260, 25194, 41990, 58786, 58786}, {0, 1, 12, 77, 350, 1260, 3808, 9996, 23256, 48450, 90440, 149226, 208012, 208012}, {0, 1, 13, 90, 440, 1700, 5508, 15504, 38760, 87210, 177650, 326876, 534888, 742900, 742900}, {0, 1, 14, 104, 544, 2244, 7752, 23256, 62016, 149226, 326876, 653752, 1188640, 1931540, 2674440, 2674440}, {0, 1, 15, 119, 663, 2907, 10659, 33915, 95931, 245157, 572033, 1225785, 2414425, 4345965, 7020405, 9694845, 9694845}, {0, 1, 16, 135, 798, 3705, 14364, 48279, 144210, 389367, 961400, 2187185, 4601610, 8947575, 15967980, 25662825, 35357670, 35357670}, {0, 1, 17, 152, 950, 4655, 19019, 67298, 211508, 600875, 1562275, 3749460, 8351070, 17298645, 33266625, 58929450, 94287120, 129644790, 129644790}, { 0, 1, 18, 170, 1120, 5775, 24794, 92092, 303600, 904475, 2466750, 6216210, 14567280, 31865925, 65132550, 124062000, 218349120, 347993910, 477638700, 477638700}, {0, 1, 19, 189, 1309, 7084, 31878, 123970, 427570, 1332045, 3798795, 10015005, 24582285, 56448210, 121580760, 245642760, 463991880, 811985790, 1289624490, 1767263190, 1767263190}, /* Here is the first row with a value > 4294967295. Let's comment the rest out, so we might have a slightly faster program. */ /* {0, 1, 20, 209, 1518, 8602, 40480, 164450, 592020, 1924065, 5722860, 15737865, 40320150, 96768360, 218349120, 463991880, 927983760, 1739969550, 3029594040, 4796857230, 6564120420, 6564120420}, {0, 1, 21, 230, 1748, 10350, 50830, 215280, 807300, 2731365, 8454225, 24192090, 64512240, 161280600, 379629720, 843621600, 1771605360, 3511574910, 6541168950, 11338026180, 17902146600, 24466267020, 24466267020}, {0, 1, 22, 252, 2000, 12350, 63180, 278460, 1085760, 3817125, 12271350, 36463440, 100975680, 262256280, 641886000, 1485507600, 3257112960, 6768687870, 13309856820, 24647883000, 42550029600, 67016296620, 91482563640, 91482563640}, {0, 1, 23, 275, 2275, 14625, 77805, 356265, 1442025, 5259150, 17530500, 53993940, 154969620, 417225900, 1059111900, 2544619500, 5801732460, 12570420330, 25880277150, 50528160150, 93078189750, 160094486370, 251577050010, 343059613650, 343059613650}, {0, 1, 24, 299, 2574, 17199, 95004, 451269, 1893294, 7152444, 24682944, 78676884, 233646504, 650872404, 1709984304, 4254603804, 10056336264, 22626756594, 48507033744, 99035193894, 192113383644, 352207870014, 603784920024, 946844533674, 1289904147324, 1289904147324}, {0, 1, 25, 324, 2898, 20097, 115101, 566370, 2459664, 9612108, 34295052, 112971936, 346618440, 997490844, 2707475148, 6962078952, 17018415216, 39645171810, 88152205554, 187187399448, 379300783092, 731508653106, 1335293573130, 2282138106804, 3572042254128, 4861946401452, 4861946401452}, {0, 1, 26, 350, 3248, 23345, 138446, 704816, 3164480, 12776588, 47071640, 160043576, 506662016, 1504152860, 4211628008, 11173706960, 28192122176, 67837293986, 155989499540, 343176898988, 722477682080, 1453986335186, 2789279908316, 5071418015120, 8643460269248, 13505406670700, 18367353072152, 18367353072152}, {0, 1, 27, 377, 3625, 26970, 165416, 870232, 4034712, 16811300, 63882940, 223926516, 730588532, 2234741392, 6446369400, 17620076360, 45812198536, 113649492522, 269638992062, 612815891050, 1335293573130, 2789279908316, 5578559816632, 10649977831752, 19293438101000, 32798844771700, 51166197843852, 69533550916004, 69533550916004}, {0, 1, 28, 405, 4030, 31000, 196416, 1066648, 5101360, 21912660, 85795600, 309722116, 1040310648, 3275052040, 9721421440, 27341497800, 73153696336, 186803188858, 456442180920, 1069258071970, 2404551645100, 5193831553416, 10772391370048, 21422369201800, 40715807302800, 73514652074500, 124680849918352, 194214400834356, 263747951750360, 263747951750360}, {0, 1, 29, 434, 4464, 35464, 231880, 1298528, 6399888, 28312548, 114108148, 423830264, 1464140912, 4739192952, 14460614392, 41802112192, 114955808528, 301758997386, 758201178306, 1827459250276, 4232010895376, 9425842448792, 20198233818840, 41620603020640, 82336410323440, 155851062397940, 280531912316292, 474746313150648, 738494264901008, 1002242216651368, 1002242216651368}, {0, 1, 30, 464, 4928, 40392, 272272, 1570800, 7970688, 36283236, 150391384, 574221648, 2038362560, 6777555512, 21238169904, 63040282096, 177996090624, 479755088010, 1237956266316, 3065415516592, 7297426411968, 16723268860760, 36921502679600, 78542105700240, 160878516023680, 316729578421620, 597261490737912, 1072007803888560, 1810502068789568, 2812744285440936, 3814986502092304, 3814986502092304}, {0, 1, 31, 495, 5423, 45815, 318087, 1888887, 9859575, 46142811, 196534195, 770755843, 2809118403, 9586673915, 30824843819, 93865125915, 271861216539, 751616304549, 1989572570865, 5054988087457, 12352414499425, 29075683360185, 65997186039785, 144539291740025, 305417807763705, 622147386185325, 1219408876923237, 2291416680811797, 4101918749601365, 6914663035042301, 10729649537134605, 14544636039226909, 14544636039226909}, {0, 1, 32, 527, 5950, 51765, 369852, 2258739, 12118314, 58261125, 254795320, 1025551163, 3834669566, 13421343481, 44246187300, 138111313215, 409972529754, 1161588834303, 3151161405168, 8206149492625, 20558563992050, 49634247352235, 115631433392020, 260170725132045, 565588532895750, 1187735919081075, 2407144796004312, 4698561476816109, 8800480226417474, 15715143261459775, 26444792798594380, 40989428837821289, 55534064877048198, 55534064877048198} */ }; /* floor_log_2(55534064877048198); = 552^64; = 18446744073709551616 */ RANK CatalanRank(SIZE n,TBBS a) { int y = -1; int r = 0; RANK lo = 0; while(a > 0) { if(0 == (a & 1)) { r++; lo += CatTriangle(r,y); } else { y++; } a >>= 1; } /* RETURN((binomial(2*n,n)/(n+1))-(lo+1)); */ return(Cat(n)-(lo+1)); } TBBS CatalanUnrank(SIZE n,RANK r) { int t = n; int y = n-1; RANK lo = 0; TBBS a = 0; r = Cat(n)-(r+1); while(t > 0) { RANK m = CatTriangle(t,y); if(r < (lo+m)) { y--; a <<= 1; a++; } else { lo += m; t--; a <<= 1; } } return(a); } /* We could as well compute it on runtime, of course... */ void CheckTriangle(int upto_n) { int r,m; for(r=0; r <= upto_n; r++) { for(m=0; m < r; m++) { if((CatTriangle(r,m-1) + CatTriangle(r-1,m)) != CatTriangle(r,m)) { fprintf(stderr,"(CatTriangle(%d,%d) + CatTriangle(%d,%d)) = %llu differs from CatTriangle(%d,%d) = %llu\n", r,(m-1),(r-1),m,(CatTriangle(r,m-1) + CatTriangle(r-1,m)), r,m,CatTriangle(r,m)); exit(1); } } if((r > 0) && (CatTriangle(r,m) != CatTriangle(r,m-1))) { fprintf(stderr,"(CatTriangle(%d,%d) = %llu differs from CatTriangle(%d,%d) = %llu\n", r,m,CatTriangle(r,m),r,(m-1),CatTriangle(r,m-1)); exit(1); } } fprintf(stderr,"Triangle OK!\n"); } void CheckRankings(int upto_n) /* Well, superficially... */ { int n; RANK r,r2,uplim; for(n=0; n <= upto_n; n++) { uplim = Cat(n); for(r=0; r < uplim; r++) { TBBS tbs = CatalanUnrank(n,r); printf("%llu ",tbs); r2 = CatalanRank(n,tbs); if(r2 != r) { fprintf(stderr,"CatalanRank(%d,%llu) gives %lu != %lu\n",n,tbs,r2,r); exit(1); } } printf("\n"); } fprintf(stderr,"Ranking & Unranking OK upto n=%d.\n", upto_n); } #define kth_byte(n) ((n) >> 3) #define ith_bit_in_byte(n) (1 << ((n) & 7)) #define toggle_bit_on(B,n) (B[kth_byte(n)] |= ith_bit_in_byte(n)) #define bit_is_zero(B,n) (0 == (B[kth_byte(n)] & ith_bit_in_byte(n))) int pos_of_first_zero_bit(BYTE *flags,int uplim) { int i; for(i=0; i < uplim; i++) { if(bit_is_zero(flags,i)) { return(i); } } return(-1); } void CountCycles(int n, PFGATOTBBS gatomorphism) { int uplim = Cat(n); int bytes_needed = (uplim >> 3)+1; BYTE *flags = ((BYTE *) calloc(bytes_needed,sizeof(BYTE))); int ff; /* First Fresh */ int cycles=0; int fixed=0; int maxcyc=0; if(NULL == flags) { fprintf(stderr,"Couldn't allocate a chunk of %u bytes to store Cat(%d) = %d bits!\n", bytes_needed,n,Cat(n)); exit(1); } if(glob_opt_out_cycle_lists) { printf("("); } while(-1 != (ff = pos_of_first_zero_bit(flags,uplim))) { int c = 0; RANK r = ((RANK) ff); TBBS tbs = CatalanUnrank(n,r); do { c++; toggle_bit_on(flags,r); tbs = gatomorphism(tbs); r = CatalanRank(n,tbs); } while(bit_is_zero(flags,r)); if(glob_opt_out_cycle_lists) { if(0 != maxcyc) { printf(" "); } printf("%d",c); } cycles++; if(1 == c) { fixed++; } if(c > maxcyc) { maxcyc = c; } } if(glob_opt_out_cycle_lists) { printf("); "); } printf("%d %d %d\n", cycles,fixed,maxcyc); fflush(stdout); free(flags); } TBBS gatotbbs_A057164(TBBS a); void main(int argc, char **argv) { ULLI x = (ULLI) (((SLLI) -1)); char *tharg; printf("%llu\n", x); CheckTriangle(19); while((tharg = *++argv) && ('-' == *tharg)) { char c; switch(c=*(tharg+1)) { case 'l': { glob_opt_out_cycle_lists = 0; break; } default: { fprintf(stderr,"Unknown option %s !\n",tharg); exit(1); } } } /* if(argc > 1) { CheckRankings(atoi(*(argv+1))); } */ if(NULL != (tharg = *argv)) { int upto_n = atoi(tharg); int n; for(n=0; n <= upto_n; n++) { CountCycles(n, gatotbbs_A057164); } } } /* Just reverse and complement the totally balanced binary string. */ TBBS gatotbbs_A057164(TBBS a) { TBBS b = 0; while(0 != a) { b <<= 1; b |= ((a^1)&1); a >>= 1; } return(b); } /* # Starting from the bit-0 (supposed to be 1), # this gives the totally balanced subsequence # of 1's and 0's (contained by that "root"), # followed by additional zero. # Count c contains the count of surplus 0's, each # 1 will decrement, and each 0 increment it by one. # When it gets to 1 we stop. NextSubBinTree := proc(nn) local n,z,c; n := nn; c := 0; z := 0; while(c < 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); od; RETURN(z); end; BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2)); BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+binwidth(BinTreeLeftBranch(n)))))); ReflectBinTree := n -> ReflectBinTree2(n)/2; ReflectBinTree2 := n -> (`if`((0 = n),n,ReflectBinTreeAux(binrev(n)))); ReflectBinTreeAux := proc(n) local a,b; a := ReflectBinTree2(BinTreeLeftBranch(n)); b := ReflectBinTree2(BinTreeRightBranch(n)); RETURN((2^(binwidth(b)+binwidth(a))) + (b * (2^(binwidth(a)))) + a); end; */