3

我需要创建一个所有排列的列表，但不包括那些有相同数量的符号改变的排列。

例如，从序列

[-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 个元素（正面和负面）的列表，则代码使用的时间非常长，我想问你一个多线程解决方案（所以我可以将代码加载到具有多个内核的集群中）......这可行吗？

4

5 回答 5

10

您基本上是在问如何组合permutationand 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/，您可能会找到一个明确的公式。

于 2012-05-29T17:14:20.380 回答
6

以下使用与您的代码相同的拒绝方法，但效率更高：

(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在上面的示例中）。

我能想到的唯一算法改进是从原始序列中删除重复的数字。这是否对您有很大帮助取决于您是否喜欢一开始就复制。

于 2012-05-29T16:36:52.180 回答
1

我想了更多，我想你会喜欢这个：

from collections import defaultdict
from itertools import permutations, product

def make_groups(seq):
    found = defaultdict(set)
    for num in seq:
        found[abs(num)].add(num)
    return [list(v) for v in found.itervalues()]

def selective_permutations(seq, r=None):
    for g in permutations(make_groups(seq), r):
        for p in product(*g):
            yield p

它采用您的输入序列 - 例如[-2, -1, 0, 1, 2]- 并将其按互斥值分组 - so [[-2, 2], [-1, 1], [0]]。

然后它permutations在组上运行 - 例如，您将得到[[-2, 2], [-1, 1]]- 然后product针对生成的组运行 yielding [[-2, -1], [-2, 1], [2, -1], [2, 1]]，这就是我们正在寻找的。

它尊重 r 参数（对于序列长度），并且在平衡和不平衡序列上都进行了最有效的工作 - 例如：

for p in selective_permutations([-3,-2,1,2], 2):
    print p

结果是

(1, 2)
(1, -2)
(1, -3)
(2, 1)
(-2, 1)
(2, -3)
(-2, -3)
(-3, 1)
(-3, 2)
(-3, -2)

无需丢弃任何组合。

希望有帮助！;-)

于 2012-05-31T22:23:36.597 回答
0

假设你只想要成对的数字（如果不是，你必须用递归做一些事情），并且序列中没有相等的数字

def make_perm(sequens):
    perm_s = []
    for e1 in sequens:
        for e2 in sequens:
            if abs(e1) != abs(e2):
               perm_s += [[e1,e2]] 

    return perm_s

print make_perm([-2,-1,1,2])

输出：

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

此解决方案处理不同的项目长度。

def perm(list_to_perm,perm_l,items):
    if len(perm_l) == items:
        print perm_l
    else:
        for i in  list_to_perm:

            if i not in perm_l:
                if -i not in perm_l:
                    perm(list_to_perm,list(perm_l) +[i],items)


a = [-2,-1,1,2]
perm(a,[],2)

输出：

[-2, -1]
[-2, 1]
[-1, -2]
[-1, 2]
[1, -2]
[1, 2]
[2, -1]
[2, 1]
于 2012-05-29T19:57:11.603 回答
0

这可能看起来有点奇怪。我还在学习python。我正在复制代码，所以顺序更自然。可能有捷径。这原来是 Rosalind.info 问题的答案。我不喜欢代码，它有点吵，但它有效。

    def 有符号烫发（x）：
        如果 len(x) == 1：
            产量 x
            x[0]*=-1
            产量 x
        别的：
            对于我在范围内（len（x））：
            对于 [1, -1] 中的 s：
            y=[x[i]*s]
            对于签名Perm中的j（x [：i] + x [i + 1：]）：
              产量 y+j

然后打电话

    [x for x in signedPerm(list(set([abs(y) for y in [-1, -2, 1, 4]])))]
于 2013-07-19T09:38:44.430 回答