生成具有k个的二进制字符串序列,其中下一个字符串以两位数字不同

Question

我想知道算法生成长度为n的二进制字符串的序列,其中k个为下一个字符串,两个数字不同.

例如:

11100
11010
11001
10101
10110
10011
00111
01011
01101
01110
11100

当然,必须使用所有n \choose k二进制字符串.

Answer 1

您应该阅读我关于这种排列（除其他外）的博客文章以获取更多背景知识 - 并点击那里的一些链接。

\n\n

这是我的词典排列生成器的一个版本，根据 Steinhaus\xe2\x80\x93Johnson\xe2\x80\x93Trotter 排列生成器的生成序列而设计，它按要求执行：

\n\n

def l_perm3(items):\n    \'Generator yielding Lexicographic permutations of a list of items\'\n    if not items:\n        yield [[]]\n    else:\n        dir = 1\n        new_items = []\n        this = [items.pop()]\n        for item in l_perm(items):\n            lenitem = len(item)\n            try:\n                # Never insert \'this\' above any other \'this\' in the item \n                maxinsert = item.index(this[0])\n            except ValueError:\n                maxinsert = lenitem\n            if dir == 1:\n                # step down\n                for new_item in [item[:i] + this + item[i:] \n                                 for i in range(lenitem, -1, -1)\n                                 if i <= maxinsert]:\n                    yield new_item                    \n            else:    \n                # step up\n                for new_item in [item[:i] + this + item[i:] \n                                 for i in range(lenitem + 1)\n                                 if i <= maxinsert]:\n                    yield new_item                    \n            dir *= -1\n\nfrom math import factorial\ndef l_perm_length(items):\n    \'\'\'\\\n    Returns the len of sequence of lexicographic perms of items. \n    Each item of items must itself be hashable\'\'\'\n    counts = [items.count(item) for item in set(items)]\n    ans = factorial(len(items))\n    for c in counts:\n        ans /= factorial(c)\n    return ans\n\nif __name__ == \'__main__\':\n    n = [1, 1, 1, 0, 0]\n    print \'\\nLexicograpic Permutations of %i items: %r\' % (len(n), n)\n    for i, x in enumerate(l_perm3(n[:])):\n        print(\'%3i %r\' % (i, x))\n    assert i+1 == l_perm_length(n), \'Generated number of permutations is wrong\'  \n

\n\n

例如，上述程序的输出如下：

\n\n

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

\n