3

我想要一个函数，它会给我指定长度的所有可能的字符串，这些字符串只由零和一组成。例如：

spam(4)

应该让我：

['0110', '0111', '0001', '0011', '0010', '0101', '0100', '1110', '1100', '1101', '1010', '1011', '1001', '1000']

我试图itertools.permutations用于这项工作。所以，这就是我所做的。

def getPerms(n):
    perms = getCandidates(n)
    res = []
    for i in perms:
        res.extend(permutations(i))
    res = clean(res)
    return res

def clean(ar):
    res = []
    for i in ar:
        temp = ""
        for j in i:
            temp += j
        res.append(temp)
    return list(set(res))

def getCandidates(n):
    res = []
    for i in range(1, n):
        res.append("1"*i + "0"*(n-i))
    return res

但这是非常低效的，并且在 10 上会出现内存错误作为输入。

4

4 回答 4

8

改为使用itertools.product。

>>> import itertools
>>> [''.join(i) for i in itertools.product('01', repeat=4)]
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

使用函数（假设itertools已经导入）：

def bitGen(n):
    return [''.join(i) for i in itertools.product('01', repeat=n)]

对于较大n的 s，返回生成器可能更合适。

def bitGen(n):
    return (''.join(i) for i in itertools.product('01', repeat=n))

# Alternatively:

def bitGen(n):
    for i in itertools.product('01', repeat=n):
        yield ''.join(i)
于 2013-03-23T03:14:16.837 回答
7

显然，您只想生成位串。这是我知道的最快的方法：

for i in xrange(1, 2**n-1):
    yield '{:0{n}b}'.format(i, n=n)

这会生成每一个长度精确地n包含至少一个 1 和一个 0 的位串。

例子：

>>> def gen(n):
...     for i in xrange(1, 2**n-1):
...         yield '{:0{n}b}'.format(i, n=n)
... 
>>> list(gen(4))
['0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110']
于 2013-03-23T03:13:52.810 回答
0

除了上面的优秀答案，如果你想继续你开始的道路，这里是一个更好的实现，使用yield：

from itertools import permutations

def spam(n):
    for perm in getPerms(n):
        print perm,
    print

def getPerms(n):
    for i in getCandidates(n):
        for perm in set(permutations(i)):
            yield ''.join(perm)

def getCandidates(n):
    for i in range(1, n):
        res = "1" * i + "0" * (n - i)
        yield res

spam(4)
于 2013-03-23T03:38:53.923 回答
0

或者您可以使用递归..这具有能够生成任何 n 位 k 基数的额外优势

def bitStr(numDig, base):
 if numDig == 0: return []
 if numDig == 1: return [str(i) for i in range(0,base)]   
 return [ digit + bits for digit in bitStr(1, base)for bits in bitStr(numDig - 1, base)]

打印 (bitStr(4, 2))

于 2016-07-08T06:26:13.253 回答