0

コンテキスト - パワー フロー ネットワークのループ フローを決定するアルゴリズムの開発。

問題：

リストのリストがあります。各リストは、アルゴリズムによって決定されたネットワーク内のループを表します。残念ながら、アルゴリズムは逆の重複も検出します。

すなわち

L1 = [a, b, c, -d, -a]

L2  = [a, d, c, -b, -a]

(c は負の値であってはならないことに注意してください。ネットワークの構造と定義されたフローにより、正しく記述されています)

現在、これら 2 つのループは同等であり、ネットワーク全体で逆の構造をたどっているだけです。

リストのリストからL2を破棄しながら、L1を保持したいと思います。したがって、6 つのループのリストがあり、そのうち 3 つが逆の重複である場合、3 つすべてを保持したいと考えています。

さらに、ループは上記の形式に従う必要はありません。それは短くても長くてもかまいませんし、符号構造 (例: pos pos pos pos neg neg) がすべてのインスタンスで発生するわけではありません。

リストを逆にして絶対値を比較することで、これをソートしようとしています。

私は完全に困惑しており、どんな支援もいただければ幸いです。

mgibson によって提供されたコードの一部に基づいて、次のコードを作成できました。

def Check_Dup(Loops):
    Act = []
    while Loops:
        L = Loops.pop()
        Act.append(L)
        Loops = Popper(Loops, L)
    return Act

def Popper(Loops, L):
    for loop in Loops:
        Rev = loop[::-1]
        if all (abs(x) == abs(y) for x, y in zip(loop_check, Rev)):
            Loops.remove(loop)
    return Loops

このコードは、毎回重複を破棄するループがなくなるまで実行する必要があります。ソリューションを作成するために必要なキーが提供されたため、mgibsons の回答を受け入れています。

4

3 に答える 3

1

あなたの質問はよくわかりませんが、リストを逆にするのは簡単です。

a = [1,2]
a_rev = a[::-1]  #new list -- if you just want an iterator, reversed(a) also works.

aと の絶対値を比較するにはa_rev:

all( abs(x) == abs(y) for x,y in zip(a,a_rev) )

これは次のように簡略化できます。

all( abs(x) == abs(y) for x,y in zip(a,reversed(a)) )

ここで、これを可能な限り効率的にするために、まず絶対値に基づいて配列を並べ替えます。

your_list_of_lists.sort(key = lambda x : map(abs,x) )

これで、2 つのリストが等しくなる場合、それらはリスト内で隣接している必要があり、enumerate を使用してそれを引き出すことができることがわかりました。

def cmp_list(x,y):
    return True if x == y else all( abs(a) == abs(b) for a,b in zip(a,b) )

duplicate_idx = [ idx for idx,val in enumerate(your_list_of_lists[1:]) 
                  if cmp_list(val,your_list_of_lists[idx])  ]

#now remove duplicates:
for idx in reversed(duplicate_idx):
    _ = your_list_of_lists.pop(idx)

（サブ）リストが厳密に増加または厳密に減少している場合、これははるかに簡単になります。

lists = list(set( tuple(sorted(x)) for x in your_list_of_lists ) )
于 2012-08-22T23:54:06.460 に答える
0 
[pair[0] for pair in frozenset(sorted( (c,negReversed(c)) ) for c in cycles)]

どこ：

def negReversed(list):
    return tuple(-x for x in list[::-1])

どこcyclesにタプルが必要ですか。

これは各サイクルを取り、その複製を計算し、それらをソートします (標準的に同等のペアにします)。セットfrozenset(...)は重複を一意にします。次に、正規要素を抽出します (この場合、任意にpair[0]).

アルゴリズムが任意の場所から始まるサイクルを返す可能性があることに注意してください。この場合 (つまり、アルゴリズムが または のいずれかを返す可能性がある場合[1,2,-3]) 、これらを同等のネックレス[-3,1,2]と見なす必要があります。

ネックレスを正規化する方法はたくさんあります。上記の方法は、ネックレスを直接正規化することを気にしないため、あまり効率的ではありません。各サイクル(a,b,c,d,e)を に変換することにより、等価クラス全体を正規要素として扱うだけ{(a,b,c,d,e), (e,a,b,c,d), (d,e,a,b,c), (c,d,e,a,b), (b,c,d,e,a)}です。あなたの場合、ネガは同等であると見なされるため、各サイクルを に変換し{(a,b,c,d,e), (e,a,b,c,d), (d,e,a,b,c), (c,d,e,a,b), (b,c,d,e,a), (-a,-b,-c,-d,-e), (-e,-a,-b,-c,-d), (-d,-e,-a,-b,-c), (-c,-d,-e,-a,-b), (-b,-c,-d,-e,-a)}ます。ハッシュ可能ではないfrozensetため、パフォーマンスのために必ず使用してください。set

eqClass.pop() for eqClass in {frozenset(eqClass(c)) for c in cycles}

どこ：

def eqClass(cycle):
    for rotation in rotations(cycle):
        yield rotation
        yield (-x for x in rotation)

回転はPythonでリストをシフトする効率的な方法のようなものですが、タプルを生成します

于 2012-08-23T00:45:02.227 に答える
0

c両方向にある場合、それらがどのように同等になるかわかりません-それらの1つはでなければなりません-c

>>> a,b,c,d = range(1,5)
>>> L1 = [a, b, c, -d, -a]
>>> L2  = [a, d, -c, -b, -a]
>>> L1 == [-x for x in reversed(L2)]
True

これらの 2 つのループを 1 つの値に折りたたむ関数を記述できるようになりました。

>>> def normalise(loop):
...     return min(loop, [-x for x in reversed(L2)])
... 
>>> normalise(L1)
[1, 2, 3, -4, -1]
>>> normalise(L2)
[1, 2, 3, -4, -1]

重複を排除する良い方法は、セットを使用することです。リストをタプルに変換するだけです。

>>> L=[L1, L2]
>>> set(tuple(normalise(loop)) for loop in L)
set([(1, 2, 3, -4, -1)])
于 2012-08-23T00:49:12.987 に答える