1
2 #include "comb/partition-dist-d-asc.h"
3 #include "comb/partition-hook-prod.h"
4 // demo-include "comb/partition-conj.h"
5 #include "aux0/factorial.h"
6
7 #include "fxtio.h"
8
9 #include "jjassert.h"
10
11 #include "fxttypes.h"
12 #include "nextarg.h"
13 #include "jjassert.h"
14
15 //% OEIS sequence A218293:
16 //% standard Young tableaux with shapes corresponding to partitions into distinct parts.
17 //% Also OEIS sequences
18 //% A000085 (all tableaux, d=0),
19 //% A225121 (tableaux for partitions into distinct parts with minimal difference 2, d=0),
20
21 // Cf. seq/A003040-demo.cc
22 // Cf. comb/partition-dist-d-asc-demo.cc for partitions where parts differ by at least d
23 // Cf. comb/partition-asc-demo.cc for (all) partitions
24
25
26 //#define TIMING // uncomment to disable printing
27
28 #include "bits/bitsperlong.h"
29
30 typedef ulong Type;
31 //typedef __uint128_t Type; // if available
32
out(Type x)33 static void out(Type x)
34 {
35 if ( x==0 ) { cout << 0; return; }
36
37 const ulong m = ~0UL;
38 ulong s = sizeof(Type)/sizeof(ulong) * BITS_PER_LONG;
39 s -= BITS_PER_LONG;
40
41 while ( 0 == (m & (x >> s)) ) s -= BITS_PER_LONG;
42 ulong r = m & (x >> s);
43 cout << r;
44
45 while ( s )
46 {
47 s -= BITS_PER_LONG;
48 r = m & (x >> s);
49 cout << setfill('0') << setw(2*BYTES_PER_LONG) << r;
50 }
51
52 cout << setfill(' ');
53 }
54 // -------------------------
55
56
57 int
main(int argc,char ** argv)58 main(int argc, char **argv)
59 {
60 ulong n = 12;
61 NXARG(n, "integer partitions of n (n<=12 for 32-bit systems, else n<=20)");
62 ulong d = 1;
63 NXARG(d, "minimal difference of parts");
64
65 partition_dist_d_asc P(n, d);
66
67 ulong ct = 0;
68
69
70
71 ulong *B = new ulong[n];
72 const Type nf = factorial(n);
73 Type tbct = 0;
74
75 ulong m = P.num_parts();
76 do
77 {
78 ++ct;
79
80 Type hp = partition_asc_hook_prod<Type>(P.data(), m, B);
81 const Type t = nf / hp;
82 tbct += t;
83
84 #ifndef TIMING
85 cout << setw(3) << ct << ":";
86 // cout << " [" << setw(2) << m << "] ";
87 P.print(" ");
88
89 cout << " #=";
90 out(t);
91
92 cout << endl;
93 #endif // TIMING
94
95 jjassert( P.OK() );
96 jjassert( nf % hp == 0 ); // caused by overflow if n is too big
97 }
98 while ( (m=P.next()) );
99
100 cout << " ct=" << ct << endl;
101 cout << " tbct=";
102 out(tbct);
103 cout << endl;
104
105 delete [] B;
106
107 return 0;
108 }
109 // -------------------------
110
111 /*
112 s=1;
113 echo $(for n in $(seq 0 20); do ./bin $n $s; done | grep tbct= ) | sed 's/ tbct=/, /g;'
114 */
115
116 /*
117 A003040: Highest degree of an irreducible representation of symmetric group S_n of degree n
118
119 for n in $(seq 1 13) ; do ./bin $n 0 | cut -s -d\# -f2 | cut -d= -f2 | sort -g | tail -1; done
120
121 */
122
123
124
125 /// Emacs:
126 /// Local Variables:
127 /// MyRelDir: "demo/seq"
128 /// makefile-dir: "../../"
129 /// make-target: "1demo DSRC=demo/seq/A218293-demo.cc"
130 /// make-target2: "1demo DSRC=demo/seq/A218293-demo.cc DEMOFLAGS=-DTIMING"
131 /// End:
132