生成唯一的正整数和负整数序列的排列

Question

我有一个数字序列：

[12,10,6,4,2]

这些数字中的每一个都可以是正数或负数。

这告诉我们有 2^5 = 32 种可能的方式可以排列任何给定的 5 个数字序列的 + 或 - 符号。

如何生成所有可能的 + 或 - 序列，同时保持这些数字的顺序不变？

代码：

combs = itertools.permutations('+++++-----', 5)
combs = list(combs)

values = [12,10,6,4,2]

broadcasted = [tuple(zip(i,values)) for i in combs]

test = set()

for item in broadcasted:
    test.add(item)

print(len(test))
print(test)

输出：


32


{(('+', 12), ('+', 10), ('-', 6), ('+', 4), ('+', 2)),
 (('+', 12), ('+', 10), ('+', 6), ('-', 4), ('+', 2)), 
 (('+', 12), ('+', 10), ('+', 6), ('+', 4), ('+', 2)), 
 (('+', 12), ('+', 10), ('-', 6), ('-', 4), ('+', 2)), 
 (('-', 12), ('+', 10), ('+', 6), ('+', 4), ('-', 2)), 
 (('-', 12), ('+', 10), ('-', 6), ('-', 4), ('-', 2)), 
 (('+', 12), ('+', 10), ('+', 6), ('-', 4), ('-', 2)), 
 (('+', 12), ('+', 10), ('-', 6), ('+', 4), ('-', 2)), 
 (('-', 12), ('+', 10), ('+', 6), ('-', 4), ('-', 2)), 
 (('-', 12), ('+', 10), ('-', 6), ('+', 4), ('-', 2)), 
 (('+', 12), ('-', 10), ('+', 6), ('-', 4), ('+', 2)), 
 (('-', 12), ('+', 10), ('+', 6), ('-', 4), ('+', 2)), 
 (('-', 12), ('+', 10), ('-', 6), ('+', 4), ('+', 2)), 
 (('-', 12), ('-', 10), ('+', 6), ('+', 4), ('-', 2)), 
 (('-', 12), ('-', 10), ('-', 6), ('-', 4), ('-', 2)), 
 (('+', 12), ('-', 10), ('+', 6), ('+', 4), ('-', 2)), 
 (('-', 12), ('-', 10), ('+', 6), ('-', 4), ('+', 2)), 
 (('-', 12), ('-', 10), ('-', 6), ('+', 4), ('+', 2)), 
 (('-', 12), ('-', 10), ('+', 6), ('+', 4), ('+', 2)), 
 (('-', 12), ('-', 10), ('-', 6), ('-', 4), ('+', 2)), 
 (('+', 12), ('-', 10), ('-', 6), ('+', 4), ('-', 2)), 
 (('+', 12), ('-', 10), ('+', 6), ('-', 4), ('-', 2)),  
 (('-', 12), ('-', 10), ('+', 6), ('-', 4), ('-', 2)), 
 (('-', 12), ('-', 10), ('-', 6), ('+', 4), ('-', 2)), 
 (('+', 12), ('+', 10), ('+', 6), ('+', 4), ('-', 2)), 
 (('+', 12), ('+', 10), ('-', 6), ('-', 4), ('-', 2)), 
 (('-', 12), ('+', 10), ('+', 6), ('+', 4), ('+', 2)), 
 (('-', 12), ('+', 10), ('-', 6), ('-', 4), ('+', 2)), 
 (('+', 12), ('-', 10), ('+', 6), ('+', 4), ('+', 2)), 
 (('+', 12), ('-', 10), ('-', 6), ('-', 4), ('+', 2)), 
 (('+', 12), ('-', 10), ('-', 6), ('+', 4), ('+', 2)), 
 (('+', 12), ('-', 10), ('-', 6), ('-', 4), ('-', 2))}

虽然它可以采用所有选项的序列（即 5'+'s and 5 '-'s），但按 5 的顺序排列它们，将它们广播到给定的数字并归结为一个集合，对于一个 10 的序列来说，计算量太大了，这需要我们构建超过 300 万个排列。我怎样才能更快地做到这一点？

Answer 1

您不需要为此进行排列；符号序列是 ['+', '-'].

五个副本的 Cartesian product 的元素

>>> values = [12, 10, 6, 4, 2]
>>> from itertools import product
>>> for signs in product('+-', repeat=5):
...     t = tuple(zip(signs, values))
...     print(t)
... 
(('+', 12), ('+', 10), ('+', 6), ('+', 4), ('+', 2))
(('+', 12), ('+', 10), ('+', 6), ('+', 4), ('-', 2))
(('+', 12), ('+', 10), ('+', 6), ('-', 4), ('+', 2))
(('+', 12), ('+', 10), ('+', 6), ('-', 4), ('-', 2))
(('+', 12), ('+', 10), ('-', 6), ('+', 4), ('+', 2))
(('+', 12), ('+', 10), ('-', 6), ('+', 4), ('-', 2))
(('+', 12), ('+', 10), ('-', 6), ('-', 4), ('+', 2))
(('+', 12), ('+', 10), ('-', 6), ('-', 4), ('-', 2))
(('+', 12), ('-', 10), ('+', 6), ('+', 4), ('+', 2))
(('+', 12), ('-', 10), ('+', 6), ('+', 4), ('-', 2))
(('+', 12), ('-', 10), ('+', 6), ('-', 4), ('+', 2))
(('+', 12), ('-', 10), ('+', 6), ('-', 4), ('-', 2))
(('+', 12), ('-', 10), ('-', 6), ('+', 4), ('+', 2))
(('+', 12), ('-', 10), ('-', 6), ('+', 4), ('-', 2))
(('+', 12), ('-', 10), ('-', 6), ('-', 4), ('+', 2))
(('+', 12), ('-', 10), ('-', 6), ('-', 4), ('-', 2))
(('-', 12), ('+', 10), ('+', 6), ('+', 4), ('+', 2))
(('-', 12), ('+', 10), ('+', 6), ('+', 4), ('-', 2))
(('-', 12), ('+', 10), ('+', 6), ('-', 4), ('+', 2))
(('-', 12), ('+', 10), ('+', 6), ('-', 4), ('-', 2))
(('-', 12), ('+', 10), ('-', 6), ('+', 4), ('+', 2))
(('-', 12), ('+', 10), ('-', 6), ('+', 4), ('-', 2))
(('-', 12), ('+', 10), ('-', 6), ('-', 4), ('+', 2))
(('-', 12), ('+', 10), ('-', 6), ('-', 4), ('-', 2))
(('-', 12), ('-', 10), ('+', 6), ('+', 4), ('+', 2))
(('-', 12), ('-', 10), ('+', 6), ('+', 4), ('-', 2))
(('-', 12), ('-', 10), ('+', 6), ('-', 4), ('+', 2))
(('-', 12), ('-', 10), ('+', 6), ('-', 4), ('-', 2))
(('-', 12), ('-', 10), ('-', 6), ('+', 4), ('+', 2))
(('-', 12), ('-', 10), ('-', 6), ('+', 4), ('-', 2))
(('-', 12), ('-', 10), ('-', 6), ('-', 4), ('+', 2))
(('-', 12), ('-', 10), ('-', 6), ('-', 4), ('-', 2))

对于大小为10的序列，笛卡尔积将有2¹⁰ = 1,024个元素，这是完全可行的。

Answer 2

我要赌这个结果格式更容易使用（如果不适合你，那么也许适合其他人）。

>>> for t in product(*((x, -x) for x in values)):
        print(t)

(12, 10, 6, 4, 2)
(12, 10, 6, 4, -2)
(12, 10, 6, -4, 2)
(12, 10, 6, -4, -2)
(12, 10, -6, 4, 2)
(12, 10, -6, 4, -2)
...
(-12, -10, -6, -4, -2)

例如，您可以轻松地使用它来计算所有可能的总和：

>>> set(map(sum, product(*((x, -x) for x in values))))
{34, 2, -6, -30, 6, -26, 10, -22, 14, -18, 18, -14, -34, 22, -2, -10, 26, 30}

正如 kaya3 评论的那样，您甚至可以使用 {x, -x} 以便 x=0 导致 {0}。输入中的每个零都会使输出元组的数量减半。

生成唯一的正整数和负整数序列的排列

Generating permutations of a unique sequence of positive and negative integers

python

iteration

combinations

permutation

sequence