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.
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]
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.
0 and 1.0000 1001 0011 1010 0110 1111 0101 1100
This will generate exactly half of the n-bit strings. This is the most you can get - the other half cannot be generated because, for instance, starting with a string of all 0's and changing two bits at a time, there will always be an even number of 1's.
