OK, here is my solution so far -- based solely on Euler cycles. Thanks to Per's post somewhere here I did figure out the way to generate lex-smallest Euler cycl.e The only problem is that this code works for n <= 20, and for n=21 stack overflows. Any ideas how to improve the code?
Code: Select all
/*
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 21
#define Q (1UL<<N)
#define BIT(k) (1UL << (k))
#define MASK(k) (BIT(k)-1UL)
#define TST(u,k) ((u) & BIT(k))
#define CLR(u,k) ((u)&=~BIT(k))
#define SET(u,k) ((u)|=BIT(k))
#define E(u,t) ((t) | ((u)<<1))
#define adj(u,t) ( (t) | (((u)<<1)&MASK(n-1)) )
#define USED(u) (TST(a[(u)>>3],(u)&7UL))
#define SET_USED(u) (SET(a[(u)>>3],(u)&7UL))
#define UNSET(u) (CLR(a[(u)>>3],(u)&7UL))
#define HAS_EDGES(u) (!USED(E(u,0))||!USED(E(u,1)))
enum { L, R };
typedef struct cell {
struct cell *nx[2];
unsigned int u;
} cell;
cell pool[Q+8],*next;
cell *init( unsigned int u ) {
cell *x = next++;
x->u = u, x->nx[L] = x->nx[R] = NULL;
return x;
}
typedef struct {
cell *head,*tail;
size_t cnt;
} deque;
deque *dinit() {
deque *q = (deque *)malloc(sizeof *q);
q->head = q->tail = NULL, q->cnt = 0;
return q;
}
void add_after( cell **item, unsigned int u ) {
cell *p = init(u);
if ( !*item )
*item = p;
else {
if ( p->nx[R] = (*item)->nx[R] )
(*item)->nx[R]->nx[L] = p;
(*item)->nx[R] = p, p->nx[L] = *item;
}
}
void push( deque *q, unsigned int u ) {
add_after(&q->tail,u);
(!q->cnt++)?(q->head=q->tail):(q->tail=q->tail->nx[R]);
}
unsigned char a[(Q>>3)+0x400],tr[(Q>>3)+0x400];
int n,K,cnt,SIMPLE_CYCLES;
unsigned int *res[N+1],q[Q+0x400],*ptr,*str,src;
deque *B;
int visit( unsigned int u ) {
if ( u == src && ptr-q > 0 )
return 1;
if ( !HAS_EDGES(u) )
return 0;
if ( !USED(E(u,0)) ) {
SET_USED(E(u,0)), *ptr++ = adj(u,0);
if ( visit(adj(u,0)) )
return 1;
UNSET(E(u,0)), --ptr;
}
if ( !USED(E(u,1)) ) {
SET_USED(E(u,1)), *ptr++ = adj(u,1);
if ( visit(adj(u,1)) )
return 1;
UNSET(E(u,1)), --ptr;
}
return 0;
}
void euler_cycle() {
unsigned int u,v,i,j,k,l;
cell *qtr;
memset(a,0,sizeof(a)), memset(tr,0,sizeof(tr)), cnt = 0;
B = dinit(), next = pool;
ptr = q, src = 0, visit(0);
for ( push(B,0), i = 0; i < ptr-q; ++i ) {
if ( !TST(tr[q[i]>>3],q[i]&7UL) )
if ( HAS_EDGES(q[i]) )
SET(tr[q[i]>>3],q[i]&7UL), ++cnt;
if ( TST(tr[q[i]>>3],q[i]&7UL) )
if ( !HAS_EDGES(q[i]) )
CLR(tr[q[i]>>3],q[i]&7UL), --cnt;
push(B,q[i]);
}
for ( qtr = B->tail; cnt; ) {
for(;qtr && !TST(tr[qtr->u>>3],qtr->u&7UL); qtr = qtr->nx[L] );
assert( qtr );
src = u = qtr->u, ptr = q;
assert( visit(u) );
for (l=(qtr==B->tail), i = 0; i < ptr-q; ++i ) {
add_after(&qtr,q[i]);
if ( !TST(tr[q[i]>>3],q[i]&7UL) )
if ( HAS_EDGES(q[i]) )
SET(tr[q[i]>>3],q[i]&7UL), ++cnt;
if ( TST(tr[q[i]>>3],q[i]&7UL) )
if ( !HAS_EDGES(q[i]) )
CLR(tr[q[i]>>3],q[i]&7UL), --cnt;
qtr = qtr->nx[R], ++B->cnt;
}
if ( l ) B->tail = qtr;
}
0 && printf("[n = %d] bsize %u\n",n,B->cnt);
assert( B->cnt == BIT(n)+1 );
res[n] = (unsigned int *)calloc(B->cnt+2,sizeof *res[n]);
for ( str = res[n], qtr = B->head; qtr; qtr = qtr->nx[R] )
*str++ = qtr->u;
for ( i = 0; i+1 < B->cnt; ++i )
res[n][i] = E(res[n][i],res[n][i+1]&1UL);
}
int main() {
int m,ts;
for ( n = 2; n <= N; ++n ) {
euler_cycle();
}
for ( scanf("%d",&ts); ts--; ) {
scanf("%d %d",&n,&m);
if ( n == 1 ) {
printf("%c\n",m+'0');
continue ;
}
printf("%u\n",res[n][m]);
}
return 0;
}