algorithm - Permutations of binary number by swapping two bits (not lexicographically)

Question

I'm looking for an algorithm which computes all permutations of a bitstring of given length (n) and amount of bits set (k). For example while n=4 and k=2 the algorithm shall output:

1100
1010
1001
0011
0101
0110

I'm aware of Gosper's Hack which generates the needed permutations in lexicographic order. But i need them to be generated in such a manner, that two consecutive permutations differ in only two (or at least a constant number of) bitpositions (like in the above example). Another bithack to do that would be awesome, but also a algorithmic description would help me alot.

Answer 1

Walking bit algorithm

To generate permutations of a binary sequence by swapping exactly one set bit with an unset bit in each step (i.e. the Hamming distance between consecutive permutations equals two), you can use this "walking bit" algorithm; the way it works is similar to creating the (reverse) lexicographical order, but the set bits walk 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

A recursive algorithm would receive a sequence of n bits, with k bits set, either all on the left or all on the right. It would then keep a 1 at the end, recurse with the rest of the sequence, move the set bit and keep 01 at the end, recurse with the rest of the bits, move the set bit and keep 001 at the end, etc... until the last recursion with only set bits. As you can see, this creates alternating left-to-right and right-to-left recursions.
When the algorithm is called with a sequence with only one bit set, this is the deepest recursion level, and the set bit walks 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);