I have been a great fan of Dr. Knuth's paper about Dancing Links (Algorithm X) . In that paper Don suggests how the combinatorial search using backtracking can be improved in practice with the original idea from Hitotumatu and Noshita. One strange thing about Dancing Links is that its not Don's original idea, however Don made it popular by writing a paper about it. Don used the $DLX$ idea to solve the exact cover (matrix cover) problem and he gave several examples (e.g. Covering an rectilinear area with Pentominos) where he certain combinatorial problems to exact cover.
I have been waiting to find a problem where I get to apply $DLX$ without reducing it to exact cover problem. I'm really happy now that simultaneous hamming neighborhood problem (given a set $S=\{s_1,s_2\ldots s_n\},\, s_i\in \Sigma^{l}$ of strings compute the set $N_d(S) = \{ t | hamming(s_i,t)\leq d ,\forall s_i \in S\}$) which I have been working lately can be solved by applying $DLX$. As I mentioned in my earlier post the algorithm to compute $N_d(S)$ needs solve a set partition problem -- which further needs an algorithm to enumerate all the subsets of a given size $r$. In my previous post we have seen how to compute $n \choose r$ efficiently with backtracking. I'm now going use $DLX$ to solve the same problem. Notice that $DLX$ is an overkill to this simple problem, however it really makes sense if we look it from the perspective of the partitioning problem -- which is what we want to solve. $DLX$ just plays the role of UNDO operation see below.
/*Implementation of $n \choose r$ using $DLX$*/
enum_count_t EnumSubSetsCountDLX(size_t n, size_t r){
enum_count_t n_choose_r=0;
DLXState *dlx_sentinal = GetEnumSubSetsDLXState(n); /*Initialize the DLXState*/
DLXState *sidx_dat[r+1], **state_idx=sidx_dat; /*item picked in the state*/
/*total # of items picked in a given state*/
size_t scidx_dat[r+1], *state_count_idx=scidx_dat;
size_t level;
state_count_idx--; state_idx--; /*1-indexing*/
level=1; state_count_idx[level]=0; state_idx[level] = dlx_sentinal;
while(level){
if(level == r+1){
n_choose_r++;
level--;
if(level) Dance(state_idx[level]);
}else if(state_count_idx[level]+r-level > n-1){ /*state_idx[level]*/
level--;
if(level) Dance(state_idx[level]);
}else{
state_idx[level] = state_idx[level]->right;
Break(state_idx[level]);
state_count_idx[level]++;
/*track forward*/
state_count_idx[level+1] = state_count_idx[level];
state_idx[level+1] = state_idx[level];
level++;
}
}
CleanDLXState(dlx_sentinal); /*cleanup*/
return n_choose_r;
}
/*Break and Dance operations*/
void Break(DLXState *state){
state->left->right = state->right;
state->right->left = state->left;
}
void Dance(DLXState *state){
state->left->right = state;
state->right->left = state;
}
/*Initializes a new DLX state required to enumerate $n \choose r$*/
EnumSubSetState* GetNewEnumSStateWithDLX(DLXState *dlx_sentinal,
size_t n, size_t r){
EnumSubSetState *estate = malloc(sizeof(EnumSubSetState));
assert(estate);
estate->dlx_sentinal = dlx_sentinal;
estate->state_count_idx = malloc(sizeof(size_t)*(r+1));
estate->state_idx = malloc(sizeof(DLXState *)*(r+1));
assert(estate->state_count_idx && estate->state_idx);
(estate->state_count_idx)--; (estate->state_idx)--;
estate->level=1; estate->state_count_idx[1]=0;
estate->state_idx[1] = estate->dlx_sentinal;
estate->n = n; estate->r = r;
return estate;
}
Next I'll post the most interesting part which is to enumerate the partitions using $DLX$.