Generating sequence of binary strings with k ones where next string differs in two digits

Question

I am wondering about algorithm generating sequence of binary strings of length n with k ones where next string differs in two digits.

For example:

11100
11010
11001
10101
10110
10011
00111
01011
01101
01110
11100

Of course, there must be used all n \choose k binary strings.

Answer 1

You should read my blog post on this kind of permutation (amongst other things) to get more background - and follow some of the links there.

Here is a version of my Lexicographic permutations generator fashioned after the generation sequence of Steinhaus–Johnson–Trotter permutation generators that does as requested:

def l_perm3(items):
    'Generator yielding Lexicographic permutations of a list of items'
    if not items:
        yield [[]]
    else:
        dir = 1
        new_items = []
        this = [items.pop()]
        for item in l_perm(items):
            lenitem = len(item)
            try:
                # Never insert 'this' above any other 'this' in the item 
                maxinsert = item.index(this[0])
            except ValueError:
                maxinsert = lenitem
            if dir == 1:
                # step down
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem, -1, -1)
                                 if i <= maxinsert]:
                    yield new_item                    
            else:    
                # step up
                for new_item in [item[:i] + this + item[i:] 
                                 for i in range(lenitem + 1)
                                 if i <= maxinsert]:
                    yield new_item                    
            dir *= -1

from math import factorial
def l_perm_length(items):
    '''\
    Returns the len of sequence of lexicographic perms of items. 
    Each item of items must itself be hashable'''
    counts = [items.count(item) for item in set(items)]
    ans = factorial(len(items))
    for c in counts:
        ans /= factorial(c)
    return ans

if __name__ == '__main__':
    n = [1, 1, 1, 0, 0]
    print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
    for i, x in enumerate(l_perm3(n[:])):
        print('%3i %r' % (i, x))
    assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'  

The output from the above program is the following for example:

Lexicograpic Permutations of 5 items: [1, 1, 1, 0, 0]
  0 [1, 1, 1, 0, 0]
  1 [1, 1, 0, 1, 0]
  2 [1, 0, 1, 1, 0]
  3 [0, 1, 1, 1, 0]
  4 [0, 1, 1, 0, 1]
  5 [1, 0, 1, 0, 1]
  6 [1, 1, 0, 0, 1]
  7 [1, 0, 0, 1, 1]
  8 [0, 1, 0, 1, 1]
  9 [0, 0, 1, 1, 1]

Answer 2

I think you can set this up using recursion.

I was inspired by the following identity:

choose(n,k) = choose(n-1,k-1) + choose(n-1,k)

So we define a function F(n,k) that produces the requested sequence (i.e., a sequence of binary strings of length n with exactly k bits set, such that successive strings differ by two bits).

First, observe that we can reorder the columns of F(n,k) any way we like and produce another, equally valid, F(n,k).

The identity above suggests we build F(n,k) using F(n-1,k-1) and F(n-1,k). Let A be strings obtained by reordering the columns of F(n-1,k-1) so that the last string ends in k-1 1s, then adding a 1 to each. Let B be the strings obtained by reordering the columns of F(n-1,k) so that the first string ends in k 1s, then adding a 0 to each. Then F(n,k) is just the concatenation of A and B. The result is a valid F(n,k), as internal to A and B the strings differ by two bits, and the last string of A and the first string of B differ by two bits (the k+1th to last bit and the last bit).

I will show an example using n=5,k=2. We get by recursion the following two F sequences:

F(4,1): 0001
        0010
        0100
        1000

F(4,2): 0011
        0101
        1001
        1010
        0110
        1100

to make A, swap the first and last column of F(4,1) and add 1 to each:

A: 10001
   00101
   01001
   00011

to make B, no column swaps are necessary, so we just add a 0 to each row of F(4,2):

B: 00110
   01010
   10010
   10100
   01100
   11000

Then F(5,2) is just the concatenation of A and B.