Генерация перестановок уникальной последовательности положительных и отрицательных целых чисел

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 ' «+» и «5»), переставьте их в последовательности по 5, передайте их до заданных цифр и сведите в набор, это слишком вычислительно для последовательности из 10, что потребует от нас создания более 3 миллионов перестановки. Как я могу сделать это быстрее?

Answer 1

Вам не нужны перестановки для этого; последовательности знаков являются элементами декартового произведения пяти экземпляров ['+', '-'].

>>> 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 ¹⁰ = 1024 элемента, что вполне возможно.

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}. Каждый ноль на входе вдвое уменьшает количество выходных кортежей.