Python中数组中1和0的组合

Question

我想在一个二维数组里创建一些1和0的组合，像下面这样：

[[ 1, 1, 1, 1, 0, 0, 0, 0 ],
 [ 1, 1, 1, 0, 1, 0, 0, 0 ],
 [ 1, 1, 1, 0, 0, 1, 0, 0 ],
 [ 1, 1, 1, 0, 0, 0, 1, 0 ],
 [ 1, 1, 1, 0, 0, 0, 0, 1 ],
 .
 .
 .
]

这意味着我需要四个1和四个0的组合。我查看了itertools模块里的permutations()和combinations()函数，但没找到合适的函数来实现这个组合。

Answer 1

你正在生成一个多重集合的排列。

一种简单但有点笨的方法是使用itertools.permutations()，然后用一个集合来过滤掉重复的组合：

>>> from itertools import permutations
>>> seen = set()
>>> for combo in permutations([1] * 4 + [0] * 4):
...     if combo not in seen:
...         seen.add(combo)
...         print combo
...
(1, 1, 1, 1, 0, 0, 0, 0)
(1, 1, 1, 0, 1, 0, 0, 0)
(1, 1, 1, 0, 0, 1, 0, 0)
(1, 1, 1, 0, 0, 0, 1, 0)
(1, 1, 1, 0, 0, 0, 0, 1)
(1, 1, 0, 1, 1, 0, 0, 0)
# ...
(0, 0, 1, 0, 1, 0, 1, 1)
(0, 0, 1, 0, 0, 1, 1, 1)
(0, 0, 0, 1, 1, 1, 1, 0)
(0, 0, 0, 1, 1, 1, 0, 1)
(0, 0, 0, 1, 1, 0, 1, 1)
(0, 0, 0, 1, 0, 1, 1, 1)
(0, 0, 0, 0, 1, 1, 1, 1)

或者，一次性生成整个序列：

set(permutations([1] * 4 + [0] * 4))

但这样会失去permutations生成的顺序。

这里需要用集合，因为permutations()把4个1和4个0当作不同的字符来看待，换一个1和另一个1的位置也会被认为是一个独特的排列。

你也可以利用序列中的顺序，避免使用集合：

last = (1,) * 8
for combo in permutations([1] * 4 + [0] * 4):
    if combo < last:
        last = combo
        print combo

这种方法有点笨，因为它会生成2n!个排列，而我们其实只想要(2n 选择 n)个元素。对于你的情况来说，这意味着会生成40320个排列，但我们只需要70个。

Answer 2

你还可以使用 combinations 来直接生成独特的组合：

n = 8
n1 = 4
for x in itertools.combinations( xrange(n), n1 ) :
    print [ 1 if i in x else 0 for i in xrange(n) ] 

[1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 0, 1, 0, 0, 0]
[1, 1, 1, 0, 0, 1, 0, 0]
[1, 1, 1, 0, 0, 0, 1, 0]
...
[0, 0, 0, 1, 1, 1, 0, 1]
[0, 0, 0, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1]

这样做比 permutations 更有效，因为你不需要遍历那些不需要的解。

这里的意思是，你想找出在长度为8的序列中放置四个“1”的所有可能方式；这正是 组合 的定义。这个数字是 C(8,4)=8! / (4! * 4!) = 70。相比之下，使用 permutations 的方法需要遍历 8! = 40,320 个候选解。