0

それぞれが持つオブジェクトのリストと、次のようなプロパティがstartあります。end

Item 0:
Start: 1
End: 12

Item 1:
Start: 6
End: 3

Item 2:
Start: 12
End: 6

新しいリストで、各アイテムが前後にあるアイテムstartと一致するように注文したいと思います。end

したがって、この例では、次のようになります。

[Item 0] [Item 2] [Item 1]
[1   12] [12   6] [6    3]

リスト全体が逆になっているかどうかは関係ありません。

また、上記のような無関係なリストが2つ混在しているため、上記のように適切な順序になる2つの新しいリストを作成する必要があります。

私はそれを「ブルートフォース」で実装し始めるので、これらのリストを作成するために多くのクエリを実行しますが、誰かがこれを解決するためのよりエレガントな方法があるかどうか尋ねたいと思いました。この種の問題がどれほど一般的かはわかりませんが、以前に見たことがあるので、この問題に対処するためのパターンがあるかもしれません。

4

2 に答える 2

2

各開始と終了の開始/終了に完全な一致があると仮定します。

items_by_start = dict((i.start, i) for i in your_items)

ordered_items = [your_items[0]]
for _ in xrange(len(your_items)-1):
    ordered_items.append(items_by_start[ordered_items[-1].end])
于 2013-02-24T23:34:34.043 に答える
1

要素を並べ替えると、重複するアイテムがないことがわかります。startただし、 sまたはsが重複しendている場合は、より注意する必要があります(複数の解決策が可能になる場合があります)。問題は、無向グラフの連結成分でオイラーパスを見つけることと同じです。これは、各( 、)ペアをグラフエッジとして扱うことで取得できます。startend

Web上のPythonでどのように実装できるかについては十分な例があります。これはO(m)時間で簡単に実行できることに注意してください。ここで、mはエッジの数です。

また、すべての頂点の次数が偶数である場合にのみ、ユークリッドパスが存在します。グラフに多くのコンポーネントがある場合でも、これは当てはまります。

于 2013-02-25T00:12:43.747 に答える