15

私の問題が組み込みの sorted() 関数を使用して解決できるかどうか、または自分で解決する必要があるかどうかを解決しようとしています - cmp を使用する古い学校は比較的簡単でした。

私のデータセットは次のようになります:

x = [
('ビジネス', Set('フリート','住所'))
('デバイス', Set('ビジネス','モデル','ステータス','パック'))
('txn', Set('device','business','operator'))
....

ソート規則は、基本的に、Y > N、x[N][0] が x[Y][1] にない N & Y のすべての値に適用する必要があります。

cmp引数がまだ利用可能なPython 2.6を使用していますが、このPython 3を安全にしようとしています。

それで、これはいくつかのラムダマジックとキー引数を使用して行うことができますか?

-== 更新 ==-

エリとウィンストンに感謝！キーの使用がうまくいくとは思っていませんでした。または、うまくいくとしたら、理想的ではない靴べらのソリューションになるのではないかと疑っていました。

私の問題はデータベース テーブルの依存関係に関するものだったので、依存関係のリストから項目を削除するために、Eli のコードに小さな追加を行う必要がありました (適切に設計されたデータベースでは、これは起こらないでしょうが、その魔法のような完璧な世界に住んでいるのは誰でしょうか?)

私の解決策：

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, set(names of dependancies))`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source]        
    emitted = []
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(set((name,)), emitted) # <-- pop self from dep, req Py2.6
            if deps:
                next_pending.append(entry)
            else:
                yield name
                emitted.append(name) # <-- not required, but preserves original order
                next_emitted.append(name)
        if not next_emitted:
            raise ValueError("cyclic dependancy detected: %s %r" % (name, (next_pending,)))
        pending = next_pending
        emitted = next_emitted
4

4 に答える 4

17

あなたが望むものは、トポロジーソートと呼ばれます。builtin を使用して実装することは可能sort()ですが、かなり扱いにくいため、Python でトポロジカル ソートを直接実装することをお勧めします。

どうしてむずかしくなるの？ウィキ ページで 2 つのアルゴリズムを調べると、どちらも実行中の一連の「マークされたノード」に依存しています。これは、フォームに変換するのが難しい概念をsort()使用できます。 timsort は、要素が検査される順序を保証しません。回避するために、使用するソリューションは、key/cmp 関数の呼び出しごとに冗長にいくつかの情報を計算することになると (かなり) 確信しています。無国籍の問題。key=xxxcmp=xxxsort()

以下は、私が使用しているalgです（いくつかのjavascriptライブラリの依存関係をソートするため）：

編集：Winston Ewertのソリューションに基づいて、これを大幅に作り直しました

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, [list of dependancies])`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-place       
    emitted = []        
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(emitted) # remove deps we emitted last pass
            if deps: # still has deps? recheck during next pass
                next_pending.append(entry) 
            else: # no more deps? time to emit
                yield name 
                emitted.append(name) # <-- not required, but helps preserve original ordering
                next_emitted.append(name) # remember what we emitted for difference_update() in next pass
        if not next_emitted: # all entries have unmet deps, one of two things is wrong...
            raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,))
        pending = next_pending
        emitted = next_emitted

補足:この python バグ トラッカーメッセージで概説されているように、関数をにシューホーンすることが可能です。cmp()key=xxx

于 2012-07-19T15:37:30.957 に答える
6

私は次のようなトポロジカルソートを行います：

def topological_sort(items):
    provided = set()
    while items:
         remaining_items = []
         emitted = False

         for item, dependencies in items:
             if dependencies.issubset(provided):
                   yield item
                   provided.add(item)
                   emitted = True
             else:
                   remaining_items.append( (item, dependencies) )

         if not emitted:
             raise TopologicalSortFailure()

         items = remaining_items

Eli のバージョンよりも少し簡単だと思いますが、効率についてはわかりません。

于 2012-07-19T16:00:27.203 に答える
5

悪い書式設定とこの奇妙なSet型を見て... (私はそれらをタプルとして保持し、リスト項目を正しく区切りました...) ...そしてnetworkxライブラリを使用して物事を便利にします...

x = [
    ('business', ('fleet','address')),
    ('device', ('business','model','status','pack')),
    ('txn', ('device','business','operator'))
]

import networkx as nx

g = nx.DiGraph()
for key, vals in x:
    for val in vals:
        g.add_edge(key, val)

print nx.topological_sort(g)
于 2012-07-19T09:08:38.753 に答える
0

これは Winston の提案であり、docstring と小さな微調整がありdependencies.issubset(provided)、provided.issuperset(dependencies). dependenciesこの変更により、必ずしも a ではなく、任意の iterable として各入力ペアでを渡すことができますset。

私の使用例には、dictキーが項目文字列である が含まれ、各キーの値は、listそのキーが依存する項目名の です。dictが空でないことを確認したら、変更したアルゴリズムに渡すことができますiteritems()。

ウィンストンに再び感謝します。

def topological_sort(items):
    """
    'items' is an iterable of (item, dependencies) pairs, where 'dependencies'
    is an iterable of the same type as 'items'.

    If 'items' is a generator rather than a data structure, it should not be
    empty. Passing an empty generator for 'items' (zero yields before return)
    will cause topological_sort() to raise TopologicalSortFailure.

    An empty iterable (e.g. list, tuple, set, ...) produces no items but
    raises no exception.
    """
    provided = set()
    while items:
         remaining_items = []
         emitted = False

         for item, dependencies in items:
             if provided.issuperset(dependencies):
                   yield item
                   provided.add(item)
                   emitted = True
             else:
                   remaining_items.append( (item, dependencies) )

         if not emitted:
             raise TopologicalSortFailure()

         items = remaining_items
于 2016-01-26T15:56:26.213 に答える