找到 0、1 的所有组合，总和为 1 或 2，长度/大小不同

Question

我想要一个 return 0、1 组合的函数，总和为 1 或 2，长度不一。我知道总组合（在删除求和之前）遵循 2**length.

示例：长度 = 4

结果：

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

我能够使用递归函数得到最多 10 的长度。之后，python 由于递归限制而崩溃。

我确实尝试增加它，但这仍然导致程序崩溃。我希望能够进行总和为 1 或 2 的所有组合，最长为 40。

代码如下：

def recursive_comb(bits):
     """Creates all possible combinations of 0 & 1
     for a given length
     """
     test = []

     def calc_bits(bits, n=0):
         if n.bit_length() <= bits:
             comb_str = '{:0{}b}'.format(n, bits)
             comb_list = [int(elem) for elem in comb_str]
             test.append(comb_list) 
             calc_bits(bits, n + 1)

     calc_bits(bits)

     return test

all_comb = recursive_comb(4)

all_comb = [elem for elem in all_comb if ((sum(elem) == 1) or (sum(elem) == 2))]

Answer 1

你可以简单地这样做：

from itertools import permutations

length = 4
result = {p for p in permutations([0, 1]*length, length) if sum(p) in [1, 2]}

print(result)

# output:
# {(0, 0, 0, 1),
#  (0, 0, 1, 0),
#  (0, 0, 1, 1),
#  (0, 1, 0, 0),
#  (0, 1, 0, 1),
#  (0, 1, 1, 0),
#  (1, 0, 0, 0),
#  (1, 0, 0, 1),
#  (1, 0, 1, 0),
#  (1, 1, 0, 0)}

结果集包含总和为 1 或 2 的所有排列。

在 permutations 中进行了一些冗余计算，因此可能需要一段时间，具体取决于 length，但您不应该运行陷入递归/内存错误。

Answer 2

如果您不介意使用外部库 (sympy)，您可以使用这个：

from sympy.utilities.iterables import multiset_permutations

length = 4
for n in range(1, 3):
    lst = [1] * n + [0] * (length - n)
    for perm in multiset_permutations(lst):
        print(perm)

multiset_permutations 生成列表的所有不同排列，其中元素不是成对不同的。我将其用于具有所需数量 0 和 1 的列表。

如果您的列表包含许多元素，这将更有效，只需遍历所有可能的排列并使用 set 丢弃重复项。

Answer 3

这是 itertools 的另一个解决方案。对于每个长度 n，以 combinations(n, k) 种方式选择 k 个位置。这种方法不太通用 multiset_permutations 来自 sympy，但对于这种特定情况更快：

import itertools

# notation:
# n: length of a sequence
# k: number of ones

def f(n, ks):
  for k in ks:
    for idx in itertools.combinations(range(n), k):
      buf = [0] * n
      for i in idx:
        buf[i] = 1
      yield buf

result = list(f(4, [1,2]))

与 20 倍加速的比较：

from sympy.utilities.iterables import multiset_permutations


def g(n, ks):
  length = n
  for k in ks:
    lst = [1] * k + [0] * (n - k)
    for perm in multiset_permutations(lst):
        yield(perm)

assert sum(1 for _ in f(20, [1,2,3])) == sum(1 for _ in g(20, [1,2,3]))
%timeit sum(1 for _ in g(20, [1,2,3])) # 10ms
%timeit sum(1 for _ in f(20, [1,2,3])) # 500µs

找到 0、1 的所有组合，总和为 1 或 2，长度/大小不同

Find all combinations of 0, 1 that sum to 1 or 2 at varying lengths / sizes

python

recursion

combinations

permutation