所有排列的列表,但没有相反的数字

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)]

(itertools用作OP)

演示:

>>> 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编辑:

我需要找到给出所有可能的数字对的最小排列数 --OP

我不确定这是什么意思,但根据你的措辞,你几乎肯定不需要做任何这些.只需使用现有方法强制解决0到10之间的数字问题,然后将结果输入http://oeis.org/,您可能会找到一个明确的公式.

Answer 2

以下使用与代码相同的拒绝方法,但效率更高:

(s for s in itertools.permutations(l, 2) if len(set(map(abs, s))) == len(s))

l 序列在哪里

唯一棘手的一点是len(set(map(abs, s))) == len(s).它将置换的所有元素的绝对值放入集合中,并确保集合具有与置换相同的大小.

为了使速度更快,您可以len(s)使用置换的长度替换(2在上面的示例中).

我能想到的唯一算法改进是从原始序列中删除重复的数字.这对你来说是否很重要取决于你是否想要首先重复一遍.