为'n'布尔元素生成所有可能的排列，这些元素的最多'm'个元素为1或True

Question

我想生成一个包含最多两个'1'的4个元素的完整列表。

例如，我有n = 4和m = 2：

我想要所有排列中最多有两个'1'的排列：

[1,0,0,0]，[0,1,0,0]，[0,0,1,0]，[0,0,0,1]，[1,0,1,0]， [0,0,1,1]，[1,1,0,0]，[1,1,0,0]，[1,0,0,1] ......你明白了。

我试图生成所有排列的完整列表，然后执行如果SUM <3然后将它提供给我。当n很小时，它运作良好。问题是我需要为大n> 30做这件事。

正如您所看到的，迭代将转到2 ^ N并且它将不可行。

由于m较小（我使用m小于5），与所有可能的组合相比，我只需要一小部分排列。并且迭代的数量级变为N ^ M，因此在这种情况下它将是N ^ 5。

有没有一种简单的方法来生成这个列表？

[编辑：至少写而不是最多]

Answer 1

具有正确n真值的长度为m的布尔数组的排列与m返回的一组n组合的itertools.combinations组合基本相同，这是由n返回的。 （在这种情况下，m事物是m真值的指数。）

为了获得高达i真值的排列，我们只需要将i中range(m + 1)的itertools.chain.from_iterable值的组合链接在一起，这可以很容易地用

from itertools import combinations, chain
# This returns an iterator
up_to_m_of_n = lambda n, m: chain.from_iterable(combinations(range(n), i)
                                                for i in range(m+1))
# Example:
list(up_to_m_of_n(4, 2))
[(), (0,), (1,), (2,), (3,), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

完成：

from operator import setitem
from functools import reduce
up_to_m_of_n_true = lambda n, m: map(lambda inds: reduce(lambda a, ind: setitem(a, ind, True) or a,
                                                         inds, [False] * n),
                                     up_to_m_of_n(n, m))
# Example (output reformatted)
list(up_to_m_of_n_true(4,2))
[False, False, False, False]
[True, False, False, False]
[False, True, False, False]
[False, False, True, False]
[False, False, False, True]
[True, True, False, False]
[True, False, True, False]
[True, False, False, True]
[False, True, True, False]
[False, True, False, True]
[False, False, True, True]

将这些索引数组转换为布尔数组有点烦人但仍然可行：

def indices_to_boolean(n, inds):
  bools = [False] * n
  for ind in inds: bools[ind] = True
  return bools

def up_to_m_of_n_true(n, m):
  for inds in up_to_m_of_n(n, m):
    yield indices_to_boolean(inds, n)

请注意，与您的示例不同，这包括没有True值的情况。

可能过于功能的up_to_m_of_n_true可能更具可读性：

from itertools import permutations

l = list(permutations([0, 0, 1, 1]))

Answer 2

set

如果你只需要独特的那些，你可以把它包装在set(list(permutations([0, 0, 1, 1]))) ：

n

如果计算这些排列/组合的数量是您唯一关注的问题，并且您不需要在数据中使用排列的实际实例，那么只需使用数学。所有这些东西都有封闭形式的表达式，请参阅组合学。

Answer 3

不确定这是否符合您的性能预期，这是一种方法：

描述：

1. max_ones是我们将要生成的二进制序列的统一长度（例如，5）.ones是1的最大数量（例如，3）
2. max_ones，是其中一个有效排列的数量。它可以从0到ones不等。
3. 对于ones == 3（比如(1,1,1,0,0)）的每个这样的有效值，通过采用“种子”（比如set()）获得排列，产生一个迭代器，生成该“种子”序列的排列，最后，将该迭代器传递给(1,)*ones + (0,)*(n-ones)（所以它会自动避免重复）。表达式max_ones创建“种子”序列。
4. 由于'''从0到chain()不等，我们会得到很多这样的套装。我们终于将所有这些集合在一起

   import itertools as itr
   
   n = 4
   max_ones = 2
   
   my_all_atmost = set(itr.chain.from_iterable([set(itr.permutations(seed_row)) 
                                                for seed_row in {(1,)*ones + (0,)*(n-ones) 
                                                                 for ones in range(0,max_ones+1)}]))

   。

码：

n == 4, max_ones == 2)

输出:(对于

print (my_all_atmost)
{(1, 0, 0, 0), (1, 0, 1, 0), (1, 1, 0, 0), 
(0, 0, 0, 1), (1, 0, 0, 1), (0, 0, 1, 0), 
(0, 1, 0, 0), (0, 1, 1, 0), (0, 0, 0, 0), 
(0, 1, 0, 1), (0, 0, 1, 1)}

的例子：

qazxswpoi