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 個以上の数字で順列のリストを作成する必要がある場合、非常に大きくなるため...

これらの寸法で問題が発生すると思いますか?

注意：これらの順列では、さらに操作を行う必要があります（すべての可能な数のペアを与える順列の最小数を見つける必要があります）ので、それらを変数に格納する必要があると思います。アルゴリズム 結果をファイルに保存する必要があります。

...わかりました、あなたの答えはとても良いです。私はあなたの興味が好きです...今、変数「ran​​ge_items」に 30 個の要素 (正と負) のリストを使用すると、コードで使用される時間が非常に長くなります。マルチスレッド ソリューション (多くのコアを持つクラスターにコードをロードできるようにするため) をお願いしようと考えています...実現可能ですか?

4

5 に答える 5

10

permutationあなたは基本的にとを組み合わせる方法を尋ねていますproduct。次の方法は、棄却よりもはるかに効率的 (かつ単純) です。すべての順列を 1 回だけ生成してから、記号をいじります。これは、時間 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)]

( itertoolsOPはそのまま使用)

デモ：

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

これは 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、結果のグループに対して実行され、 を生成[[-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 に答える