在Python中生成唯一的二进制排列

Question

请问，在Python中如何获取所有的二进制排列，但是不重复？

 a = list(itertools.permutations([1, 1, 0, 0]))
 for i in range(len(a)):
     print a[i]

    (1, 1, 0, 0)
    (1, 1, 0, 0)
    (1, 0, 1, 0)
    ...

如果能大致高效，那就太好了，因为我将需要处理一个像这样的30个元素的列表。

- maicon

---

你正在询问“长度为N且恰好有M位设置的二进制数”。 - Antti Haapala -- Слава Україні

生成所有长度为 n 的二进制字符串，其中恰好有 k 个位设置为 1。 - Antti Haapala -- Слава Україні

相关：具有唯一值的排列 - Aran-Fey

不能讨论最好的Python解决方案及其权衡。 - Antti Haapala -- Слава Україні

我肯定是漏掉了什么，但 set(a) 是什么意思？ - shantanuo

Answer 1

正如评论中的@Antti所说，这相当于寻找输入列表中的位置的组合，这些位置确定输出中哪些位是1。

from itertools import combinations

def binary_permutations(lst):
    for comb in combinations(range(len(lst)), lst.count(1)):
        result = [0] * len(lst)
        for i in comb:
            result[i] = 1
        yield result

for perm in binary_permutations([1, 1, 0, 0]):
    print(perm)

输出：

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

- Alex Hall

---

不要太过于严格地理解MCVE，例如，如果代码仍然可以处理像[1, 1, 0, 0, 'potato']这样的输入并得出合理的结果，那就很好。 - wim

Answer 2

这里是从通用算法问题的被接受答案中引用的算法，已经改编成Python 3（可在Python 2.7+中使用）。 generate(start, n_bits) 函数将按字典顺序生成所有从start开始的 n位数 整数。

def generate(start, n_bits):
    # no ones to permute...
    if start == 0:
        yield 0
        return

    # fastest count of 1s in the input value!!
    n_ones = bin(start).count('1')

    # the minimum value to wrap to when maxv is reached;
    # all ones in LSB positions
    minv = 2 ** n_ones - 1

    # this one is just min value shifted left by number of zeroes
    maxv = minv << (n_bits - n_ones)

    # initialize the iteration value
    v = start

    while True:
        yield v

        # the bit permutation doesn't wrap after maxv by itself, so,
        if v == maxv:
            v = minv

        else:
            t = ((v | ((v - 1))) + 1)
            v = t | (((((t & -t)) // ((v & -v))) >> 1) - 1)

        # full circle yet?
        if v == start:
            break

for i in generate(12, 4):
    print('{:04b}'.format(i))

打印

1100
0011
0101
0110
1001
1010

如果生成了列表输出，那么可以进行修饰:

def generate_list(start):
    n_bits = len(start)
    start_int = int(''.join(map(str, start)), 2)

    # old and new-style formatting in one
    binarifier = ('{:0%db}' % n_bits).format

    for i in generate(start_int, n_bits): 
        yield [int(j) for j in binarifier(i)]

for i in generate_list([1, 1, 0, 0]):
    print(i)

打印

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

这个算法的好处是你可以在任何时候恢复它。如果你找到了一种计算好起始点的方法，那么它也可以并行化。而且，数字应该比列表更紧凑，所以如果可能的话，你可以使用它们。

- Antti Haapala -- Слава Україні

---

这很有趣，我很高兴你做到了，但是我感觉使用它会让我不舒服，因为我不知道它为什么有效。源代码没有解释原因，所以在某种程度上，我只是盲目地相信它有效。彻底测试一下并与其他方法进行性能比较会很好。这样也可以证明它的有效性。 - Alex Hall

Answer 3

你想要做的是选择两个位置，使得元素的值为1。

代码

from itertools import combinations

def bit_patterns(size, ones):
    for pos in map(set, combinations(range(size), ones)):
        yield [int(i in pos) for i in range(size)]

输出

>>> print(*bit_patterns(4, 2), sep='\n')
[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
[0, 1, 1, 0]
[0, 1, 0, 1]
[0, 0, 1, 1]

替代方案

一个有趣的替代方案是将所需输出视为仅具有两个1的二进制表示。我们可以使用这个定义来获得您想要的输出。

from itertools import combinations

def bit_patterns(size, ones):
    for t in combinations([1 << i for i in range(size)], ones):
        yield [int(n) for n in f'{sum(t):0{size}b}']

- Olivier Melançon

---

@AlexHall 很简单：只需计算数字的数量，生成小于 N - 1 的 2 的幂；然后计算数字中的 1 的数量；相应地更改 2 和 4。 - Antti Haapala -- Слава Україні

Answer 4

这是一个递归解决方案：

def bin_combs_iter(ones, zeros):
    if not zeros:
        yield [1] * ones
    elif not ones:
        yield [0] * zeros
    else:
        for x in bin_combs_iter(ones - 1, zeros):
            x.append(1)
            yield x
        for x in bin_combs_iter(ones, zeros - 1):
            x.append(0)
            yield x


def bin_combs(ones, zeros):
    return list(bin_combs_iter(ones, zeros))

- hilberts_drinking_problem

---

你需要递归调用bin_combs_iter，而不是bin_combs，否则对于大量的输入会使用大量的内存。 - Alex Hall