长度为x的二进制序列的所有排列组合

Question

我想找到一种干净聪明的方式（用 Python），以找到长度为 x 的由 1 和 0 组成的所有字符串的排列。理想情况下，这应该是快速的，不需要进行太多次迭代...

因此，对于 x = 1，我希望得到: ['0','1'] x =2 ['00','01','10','11'] 等等...

目前我有以下代码，但它很慢，似乎也不优雅：

    self.nbits = n
    items = []
    for x in xrange(n+1):
        ones = x
        zeros = n-x
        item = []
        for i in xrange(ones):
            item.append(1)
        for i in xrange(zeros):
            item.append(0)
        items.append(item)
    perms = set()
    for item in items:
        for perm in itertools.permutations(item):
            perms.add(perm)
    perms = list(perms)
    perms.sort()
    self.to_bits = {}
    self.to_code = {}
    for x in enumerate(perms):
        self.to_bits[x[0]] = ''.join([str(y) for y in x[1]])
        self.to_code[''.join([str(y) for y in x[1]])] = x[0]

- ComputationalSocialScience

---

请注意，您实际上并没有描述排列组合。 - Glenn Maynard

我感觉到一个代码高尔夫答案串即将到来。 :-) - payne

Answer 1

itertools.product 适用于此情况:

>>> import itertools
>>> ["".join(seq) for seq in itertools.product("01", repeat=2)]
['00', '01', '10', '11']
>>> ["".join(seq) for seq in itertools.product("01", repeat=3)]
['000', '001', '010', '011', '100', '101', '110', '111']

- Josh Bleecher Snyder

Answer 2

对于这么简单的事情，没有必要过于聪明：

def perms(n):
    if not n:
        return

    for i in xrange(2**n):
        s = bin(i)[2:]
        s = "0" * (n-len(s)) + s
        yield s

print list(perms(5))

- Glenn Maynard

Answer 3

你可以使用itertools.product()来完成这个任务。

import itertools
def binseq(k):
    return [''.join(x) for x in itertools.product('01', repeat=k)]

- Sebastian Paaske Tørholm

---

请注意，您可以使用map作为循环结构来使其更快：map(''.join, itertools.product('01', repeat=k))。 - ncoghlan

@ncoghlan，它们的功能不同。 - AMC

考虑到时间（2011年初），我可能在谈论Python 2，其中它仍然会生成一个列表。在Py3中，确实，基于map的版本将产生一个惰性迭代器而不是具体的列表（这可能是您想要的，也可能不是）。 - ncoghlan

Answer 4

Python 2.6+:

['{0:0{width}b}'.format(v, width=x) for v in xrange(2**x)]

- Ignacio Vazquez-Abrams

---

聪明，但至少在我的机器上（使用2 **（16 ... 20）的适度大小）比Josh的答案慢了约3倍。 - eat

Answer 5

之前提供的聪明解决方案都很好。这里提供一种低级别、让你动手操作的方法：

def dec2bin(n):
    if not n:
        return ''
    else:
        return dec2bin(n/2) + str(n%2)

def pad(p, s):
    return "0"*(p-len(s))+s

def combos(n):
    for i in range(2**n):
        print pad(n, dec2bin(i))

那应该就可以了。

- inspectorG4dget