1 2 #include "ds/bitarray.h" 3 4 #include "comb/comb-print.h" 5 #include "perm/permq.h" 6 7 #include "fxtio.h" 8 #include "aux0/swap.h" 9 #include "fxttypes.h" 10 11 //#include "perm/permq.h" // is_involution(), is_connected() 12 #include "jjassert.h" 13 14 #include "nextarg.h" // NXARG() 15 16 //% OEIS sequence A175498: 17 //% Greedily choose next n (minimal) such that all differences in prefix are distinct. 18 19 //#define BFILE 20 21 int main()22main() 23 { 24 #ifdef BFILE 25 const ulong off = 1; 26 #endif 27 const ulong aoff = 1; 28 29 const ulong n = 150; // set to 1500 for more than 100 terms 30 ulong *a = new ulong[n]; // sequence 31 32 const ulong N = 32*1024; 33 bitarray T(N); // which n are Taken 34 T.clear_all(); 35 36 const ulong N2 = 2 * N; 37 bitarray D(N2); // which Differences we have seen so far 38 D.clear_all(); 39 40 ulong p = 0; 41 a[p] = 0; 42 T.set(p); 43 44 #ifdef BFILE 45 cout << p+off << " " << a[p]+aoff << endl; 46 #else 47 cout << a[p]+aoff << ", "; 48 #endif 49 while ( p<n ) 50 { 51 ulong j, d=0; 52 for (j=0; j<n; ++j) 53 { 54 if ( T.test(j) ) continue; // element already taken 55 56 d = j - a[p]; 57 // if ( j < a[p] ) d = -d; // A081145 58 59 jjassert( d + N < N2 ); 60 if ( ! D.test(d+N) ) break; // difference already taken 61 } 62 if ( j==n ) break; 63 64 D.set(d+N); 65 T.set(j); 66 67 ++p; 68 a[p] = j; 69 // if ( is_valid_permutation(a, p) ) print_perm("P=",a,p); 70 71 #ifdef BFILE 72 cout << p+off << " " << a[p]+aoff << endl; 73 #else 74 cout << a[p]+aoff << ", "; 75 #endif 76 } 77 cout << endl; 78 // cout << " ct=" << p+1 << endl; 79 80 delete [] a; 81 return 0; 82 } 83 // ------------------------- 84 85 86 /// Emacs: 87 /// Local Variables: 88 /// MyRelDir: "demo/seq" 89 /// makefile-dir: "../../" 90 /// make-target: "1demo DSRC=demo/seq/A175498-demo.cc" 91 /// make-target2: "1demo DSRC=demo/seq/A175498-demo.cc DEMOFLAGS=-DTIMING" 92 /// End: 93 94