During my current research on enumerating all the common *Hamming* neighborhood of a set of strings. I needed an algorithm which can enumerate seven disjoint subsets from a given set. The fundamental building block in that is an algorithm which enumerates all the subsets of size $r$ from a given set of size $n$. I'm very much aware of the standard recursive algorithm which uses the fact
${n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}$. However I wanted a much efficient version because I need to use this several times and cannot afford the constants in stack based implementations. So I wrote the following to backtracking based algorithm to enumerate the subsets. Once I did that I started observing some very interesting patterns in the number of leaves for each internal backtrack node at level $r-1$.

/*Back tracking*/ enum_count_t EnumSubSetsPrint(char *set, size_t n, size_t r){ size_t state_idx_data[r+1], i, level; size_t *state_idx = state_idx_data; enum_count_t n_choose_r=0; set--; state_idx--; for(i=1; i<=r+1; i++){ /*initialize*/ state_idx[i] = 0; } level = 1; while(level){ if(level == r+1){ /*back track*/ for(i=1; i<=r; i++){ printf("%c ", set[state_idx[i]]); } printf("\n"); n_choose_r++; level--; }else if(state_idx[level]+r-level > n-1){ level--; }else{ /*track forward*/ state_idx[level]++; /*pick a item*/ state_idx[level+1] = state_idx[level]; level++; } } return n_choose_r; }

By looking at these patterns (at the end of this paragraph) I came up with the following interesting identities for $n \choose 3$ and $n \choose 4$.

I'm actually printing the number of leaves under an internal node at level $r-1$ in the backtracking tree. I'm observing the following pattern.

================= 8 3 0 6 5 4 3 2 1 5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 (8 \choose 3) = 56 Please enter n and r < n and print_option (e.g. 15 14 1 or 15 14 0) 9 3 0 7 6 5 4 3 2 1 6 5 4 3 2 1 5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 (9 \choose 3) = 84 Please enter n and r < n and print_option (e.g. 15 14 1 or 15 14 0) 10 3 0 8 7 6 5 4 3 2 1 7 6 5 4 3 2 1 6 5 4 3 2 1 5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 (10 \choose 3) = 120 Please enter n and r < n and print_option (e.g. 15 14 1 or 15 14 0) 11 3 0 9 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 7 6 5 4 3 2 1 6 5 4 3 2 1 5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 =============================== The following are for $n \choose 4$ for various values of $n$. =============================== 8 4 0 5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 4 3 2 1 3 2 1 2 1 1 3 2 1 2 1 1 2 1 1 1 (8 \choose 4) = 70 Please enter n and r < n and print_option (e.g. 15 14 1 or 15 14 0) 9 4 0 6 5 4 3 2 1 5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 4 3 2 1 3 2 1 2 1 1 3 2 1 2 1 1 2 1 1 1 ===============================

Play around with this program Enumerate.c , Enumerate.h.

Finally I enabled $LaTeX$ setting for the blog.

## No comments:

Post a Comment