Running bit algorithm
To create permutations of a binary sequence by replacing only one bit with a disproportionate bit at each step (ie, the Hamming distance between consecutive permutations is two), you can use this “walk” algorithm; the way it works is similar to creating a (reverse) lexicographic order, but the set bits go right and left alternately, and as a result some parts of the sequence are mirrored. This is probably better explained with an example:
Recursive implementation
The recursive algorithm will receive a sequence of n bits, with k bits set, either all on the left or all on the right. Then it will save 1 at the end, recursion with the rest of the sequence, move the set bit and save 01 at the end, recursion with the remaining bits will move the set bit and save 001 at the end, etc. until the last recursion with the bits set. As you can see, this creates alternating recursions from left to right and from right to left.
When an algorithm is called with a sequence with only one bit, this is the deepest level of recursion, and the set bit goes from one end to the other.
Code Example 1
Here's a simple recursive JavaScript implementation:
function walkingBits(n, k) { var seq = []; for (var i = 0; i < n; i++) seq[i] = 0; walk (n, k, 1, 0); function walk(n, k, dir, pos) { for (var i = 1; i <= n - k + 1; i++, pos += dir) { seq[pos] = 1; if (k > 1) walk(n - i, k - 1, i%2 ? dir : -dir, pos + dir * (i%2 ? 1 : n - i)) else document.write(seq + "<BR>"); seq[pos] = 0; } } } walkingBits(7,3);
C ++ translation, which could be something like this:
#include <iostream> #include <string> void walkingBits(int n, int k, int dir = 1, int pos = 0, bool top = true) { static std::string seq; if (top) seq.resize(n, '0'); for (int i = 1; i <= n - k + 1; i++, pos += dir) { seq[pos] = '1'; if (k > 1) walkingBits(n - i, k - 1, i % 2 ? dir : -dir, pos + dir * (i % 2 ? 1 : n - i), false); else std::cout << seq << '\n'; seq[pos] = '0'; } if (top) seq.clear(); } int main() { walkingBits(7, 3); }
(See also this version of C ++ 11 written by VolkerK in response to a question about the above code.)
Code Example 2
Or, if you prefer code where the elements of the array actually change:
function walkingBits(n, k) { var seq = []; for (var i = 0; i < n; i++) seq[i] = i < k ? 1 : 0; document.write(seq + "<BR>"); walkRight(n, k, 0); function walkRight(n, k, pos) { if (k == 1) for (var p = pos + 1; p < pos + n; p++) swap(p - 1, p) else for (var i = 1; i <= n - k; i++) { [walkLeft, walkRight][i % 2](n - i, k - 1, pos + i); swap(pos + i - 1, pos + i + (i % 2 ? 0 : k - 1)); } } function walkLeft(n, k, pos) { if (k == 1) for (var p = pos + n - 1; p > pos; p--) swap(p - 1, p) else for (var i = 1; i <= n - k; i++) { [walkRight, walkLeft][i % 2](n - i, k - 1, pos); swap(pos + n - i - (i % 2 ? 1 : k), pos + n - i); } } function swap(a, b) { var c = seq[a]; seq[a] = seq[b]; seq[b] = c; document.write(seq + "<BR>"); } } walkingBits(7,3);
Code Example 3
Here, recursion is pumped into an iterative implementation, and each of the set bits (that is, each of the recursion levels) is represented by an object {o,d,n,p} , which holds the offset from the leftmost position, the direction of the set bit is moved, the number of bits (t. e. the length of this part of the sequence) and the current position of the given bit in this part.
function walkingBits(n, k) { var b = 0, seq = [], bit = [{o: 0, d: 1, n: n, p: 0}]; for (var i = 0; i < n; i++) seq.push(0); while (bit[0].p <= n - k) { seq[bit[b].o + bit[b].p * bit[b].d] = 1; while (++b < k) { bit[b] = { o: bit[b-1].o + bit[b-1].d * (bit[b-1].p %2 ? bit[b-1].n-1 : bit[b-1].p+1), d: bit[b-1].d * (bit[b-1].p %2 ? -1 : 1), n: bit[b-1].n - bit[b-1].p - 1, p: 0 } seq[bit[b].o + bit[b].p * bit[b].d] = 1; } document.write(seq + "<BR>"); b = k - 1; do seq[bit[b].o + bit[b].p * bit[b].d] = 0; while (++bit[b].p > bit[b].n + b - k && b--); } } walkingBits(7, 3);
Converting lexicographic order into a walking bit
Since the walking bit algorithm is a variation of the algorithm for generating permutations in the (reverse) lexicographic order, each permutation in the lexicographic order can be converted to the corresponding permutation in the walking bit order by mirroring the corresponding parts of the binary sequence.
Thus, you can use any algorithm (for example, Gosper Hack) to create permutations in the lexicographic or reverse lexicographic order, and then convert each of them to get the order of the navigation bits.
In practice, this means repeating the binary sequence from left to right, and if you find the set bit after an odd number of zeros, change the rest of the sequence and iterate from right to left, etc.
Code Example 4
In the code below, permutations for n,k = 7,3 generated in reverse lexicographic order and then converted one after the other:
function lexi2walk(lex) { var seq = [], ofs = 0, pos = 0, dir = 1; for (var i = 0; i < lex.length; ++i) { if (seq[ofs + pos * dir] = lex[i]) { if (pos % 2) ofs -= (dir *= -1) * (pos + lex.length - 1 - i) else ofs += dir * (pos + 1); pos = 0; } else ++pos; } return seq; } function revLexi(seq) { var max = true, pos = seq.length, set = 1; while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false; if (pos < 0) return false; seq[pos] = 0; while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0; return true; } var s = [1,1,1,0,0,0,0]; document.write(s + " → " + lexi2walk(s) + "<br>"); while (revLexi(s)) document.write(s + " → " + lexi2walk(s) + "<br>");
Homogeneous gray path
The permutation order created by this algorithm is similar, but not identical, to that created by the "uniform gray path for combinations" algorithm described by D. Knut in "The Art of Programming" vol, 4a, section. 7.2.1.3, formula (31) and Fig. 26s