93 lines
1.6 KiB
C
93 lines
1.6 KiB
C
#include <stdio.h>
|
|
#include <stdint.h>
|
|
|
|
#define GCC_ASM // use GCC's asm for i386. If it does not work, #undef it to use alternative func
|
|
typedef uint32_t uint;
|
|
typedef uint64_t ulong;
|
|
|
|
#define MASK 0xa08228828228a2bULL
|
|
|
|
#ifdef GCC_ASM
|
|
|
|
static inline uint
|
|
bpos(uint x)
|
|
{
|
|
uint b;
|
|
asm("bsf %0, %0" : "=r" (b): "0" (x));
|
|
return b;
|
|
}
|
|
|
|
#else
|
|
|
|
static inline uint
|
|
bpos(uint x)
|
|
{
|
|
static const uint bruijin[32] = {
|
|
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
|
|
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
|
|
};
|
|
return bruijin[((uint)((x & -x) * 0x077CB531U)) >> 27];
|
|
}
|
|
|
|
#endif // GCC_ASM
|
|
|
|
int count(uint n, const uint s, uint avail)
|
|
{
|
|
int cnt = 0;
|
|
|
|
avail ^= s;
|
|
if (--n)
|
|
for (uint b = (uint)(MASK>>bpos(s)) & avail; b; b &= b-1)
|
|
cnt += count(n, b&-b, avail);
|
|
else
|
|
return (MASK & s) != 0;
|
|
|
|
return cnt;
|
|
}
|
|
|
|
int disp(uint n, const uint s, uint avail, int maxn, uint *seq)
|
|
{
|
|
seq[n--] = s;
|
|
if (!n) {
|
|
if ((MASK & s)) {
|
|
for (int i = 0; i < maxn; i++)
|
|
printf(" %d", bpos(seq[i]) + 1);
|
|
putchar('\n');
|
|
return 1;
|
|
}
|
|
} else {
|
|
for (uint b = (uint)(MASK>>bpos(s)) & (avail ^= s); b; b &= b-1)
|
|
if (disp(n, b&-b, avail, maxn, seq))
|
|
return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
int chain(uint n, int count_only)
|
|
{
|
|
const uint top = 1U<<(n - 1);
|
|
const uint avail = 2*top - 2;
|
|
|
|
if (count_only)
|
|
return count(n - 1, top, avail);
|
|
|
|
uint seq[32];
|
|
seq[0] = 1;
|
|
disp(n - 1, top, avail, n, seq);
|
|
|
|
return 0;
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
for (int n = 2; n < 21; n++)
|
|
chain(n, 0);
|
|
putchar('\n');
|
|
|
|
for (int n = 2; n < 21; n++)
|
|
printf("%d ", chain(n, 1));
|
|
putchar('\n');
|
|
|
|
return 0;
|
|
}
|