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

i'm looking algorithm computes permutations of bitstring of given length (n) , amount of bits set (k). example while n=4 , k=2 algorithm shall output:

1100 1010 1001 0011 0101 0110 

i'm aware of gosper's hack generates needed permutations in lexicographic order. need them generated in such manner, 2 consecutive permutations differ in 2 (or @ least constant number of) bitpositions (like in above example). bithack awesome, algorithmic description me alot.

walking bit algorithm

to generate permutations of binary sequence swapping 1 set bit unset bit in each step (i.e. hamming distance between consecutive permutations equals two), can use "walking bit" algorithm; way works similar creating (reverse) lexicographical order, set bits walk right , left alternately, , result parts of sequence mirrored. better explained example:

recursive implementation

a recursive algorithm receive sequence of n bits, k bits set, either on left or on right. keep 1 @ end, recurse rest of sequence, move set bit , keep 01 @ end, recurse rest of bits, move set bit , keep 001 @ end, etc... until last recursion set bits. can see, creates alternating left-to-right , right-to-left recursions.
when algorithm called sequence 1 bit set, deepest recursion level, , set bit walks 1 end other.

---

code example 1

here's simple recursive javascript implementation:

function walkingbits(n, k) {      var seq = [];      (var = 0; < n; i++) seq[i] = 0;      walk (n, k, 1, 0);        function walk(n, k, dir, pos) {          (var = 1; <= 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);

translated c++ 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');     (int = 1; <= n - k + 1; i++, pos += dir) {         seq[pos] = '1';         if (k > 1) walkingbits(n - i, k - 1, % 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 this c++11 version, written volkerk in response question above code.)

code example 2

or, if prefer code elements of array being swapped:

function walkingbits(n, k) {      var seq = [];      (var = 0; < n; i++) seq[i] = < k ? 1 : 0;      document.write(seq + "<br>");      walkright(n, k, 0);        function walkright(n, k, pos) {          if (k == 1) (var p = pos + 1; p < pos + n; p++) swap(p - 1, p)          else (var = 1; <= n - k; i++) {              [walkleft, walkright][i % 2](n - i, k - 1, pos + i);              swap(pos + - 1, pos + + (i % 2 ? 0 : k - 1));          }      }      function walkleft(n, k, pos) {          if (k == 1) (var p = pos + n - 1; p > pos; p--) swap(p - 1, p)          else (var = 1; <= n - k; i++) {              [walkright, walkleft][i % 2](n - i, k - 1, pos);              swap(pos + n - - (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 rolled out iterative implementation, each of set bits (i.e. each of recursion levels) represented object {o,d,n,p} holds offset leftmost position, direction set bit moving in, number of bits (i.e. length of part of sequence), , current position of set bit within part.

function walkingbits(n, k) {      var b = 0, seq = [], bit = [{o: 0, d: 1, n: n, p: 0}];      (var = 0; < 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;          seq[bit[b].o + bit[b].p * bit[b].d] = 0;          while (++bit[b].p > bit[b].n + b - k && b--);      }  }    walkingbits(7, 3); // n >= k > 0

transforming lexicographical order walking bit

because walking bit algorithm variation of algorithm generate permutations in (reverse) lexicographical order, each permutation in lexicographical order can transformed corresponding permutation in walking bit order, mirroring appropriate parts of binary sequence.
can use algorithm (e.g. gosper's hack) create permutations in lexicographical or reverse lexicographical order, , transform each 1 walking bit order.

practically, means iterating on binary sequence left right, , if find set bit after odd number of zeros, reversing rest of sequence , iterating on right left, , on...

code example 4

in code below permutations n,k = 7,3 generated in reverse lexicographical order, , transformed one-by-one:

function lexi2walk(lex) {      var seq = [], ofs = 0, pos = 0, dir = 1;       (var = 0; < 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 + " &rarr; " + lexi2walk(s) + "<br>");  while (revlexi(s)) document.write(s + " &rarr; " + lexi2walk(s) + "<br>");

homogeneous gray path

the permutation order created algorithm similar, not identical, 1 created "homogeneous gray path combinations" algorithm described d. knuth in the art of computer programming vol. 4a, sect. 7.2.1.3, formula (31) & fig. 26c.