python - 所有排列的列表，但没有相反的数字

Question

我需要创建所有排列的列表，但不包括符号数相同的排列。

例如从序列

[-2, -1, 1, 2]

我会得到像这样的所有排列:

[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]

目前我使用以下代码:

permutation_items = []
permutations = itertools.permutations(range_items, items)
permutation_item = list(permutations)

例如 range_items = [-2, -1, 1, 2] 和 items = 2

然后为了消除我使用的所有相反的重复项

for element in permutation_items:
    flag=0
    for j in element:
        if ((j in element) & ((j*-1) in element)):
            flag = 1
            break
    if flag == 0:
        all_solutions.append(element)

我认为这不是最好的方法，因为首先我创建了一个包含所有排列的列表，然后我删除了那些我不想要的，你能建议一个更好的方法吗？还因为如果我需要创建一个包含 10 个或更多数字的排列列表，它会变得非常大......

您认为我在这些维度上会遇到一些问题吗？

请注意:对于这些排列，我需要做进一步的操作(我需要找到给出所有可能的数字对的最小排列数)，所以我认为我需要将它们存储在一个变量中，也是因为在在我的算法结束时，我需要将结果存储在一个文件中。

...好吧，伙计们，你们的回答非常好，我喜欢你们的兴趣...现在，如果我为我的变量“range_items”使用一个包含 30 个元素(正数和负数)的列表，代码使用的时间是很大，我想问你一个多线程的解决方案(这样我就可以在一个多核的集群中加载代码)...是否可行？

Answer 1

您基本上是在询问如何组合permutation 和product。以下方法比拒绝更有效(也更简单):您只生成一次所有排列，然后旋转符号。它在时间 O(N!) 和空间 O(1) 方面是渐近最优的:

def plusAndMinusPermutations(items):
    for p in permutations(items):
        for signs in product([-1,1], repeat=len(items)):
            yield [a*sign for a,sign in zip(p,signs)]

(像 OP 一样使用 itertools)

演示:

>>> list( plusAndMinusPermutations([1,2]) )
[
 [-1, -2], 
 [-1, 2], 
 [1, -2],
 [1, 2],
 [-2, -1],
 [-2, 1],
 [2, -1],
 [2, 1]
]

这比 factorial(N) 更有效率!!! (假设您将它用于大于 2 的长度。)

或者，我们可以以相反的顺序组合它们(如果您愿意，可以将 list 映射到元组上):

def plusAndMinusPermutations(items):
    for signed in product(*[[-a,a] for a in items]):
        for p in permutations(signed):
            yield p

>>> list( plusAndMinusPermutations([1,2]) )
[
 (-1, -2), 
 (-2, -1), 
 (-1, 2), 
 (2, -1), 
 (1, -2), 
 (-2, 1), 
 (1, 2), 
 (2, 1)
]

---

响应 OP 编辑​​进行编辑:

I need to find the minimum number of permutations that give all possible couples of numbers --OP

我不确定这是什么意思，但根据您的措辞，您几乎可以肯定不需要执行任何这些操作。只需使用现有方法对 0 到 10 之间的数字进行暴力破解，然后将结果输入 http://oeis.org/。你可能会找到一个明确的公式。