ペアのリストからバッグを抽出するための効率的なアルゴリズムは何ですか？

Question

オブジェクトのペアのリストがあります。オブジェクトは、どちらの順序でペアに表示できます。同じオブジェクト間のペアのすべてのバッグ（つまり、複製が許可されている）をすべて見つけるための最も効率的なアルゴリズム（および実装？）は何ですか。私の目的のために、オブジェクトの参照はポインター、または名前、または同様の便利で短い、有用な表現であると想定できます。個々のペアは識別可能です。ペアの両方の部分に同じオブジェクトを持っているペアはありません。

したがって、ペアのリストが与えられています（OIDはオブジェクト参照です。PIDAペアリファレンス）

O1-P1-O2
O3-P2-O4
O5-P3-O1
O1-P4-O2
O2-P5-O1
O1-P6-O5
O7-P7-O8

返品する必要があります：

P1;P4;P5 and P3;P6

Answer 1

「小さい」はオブジェクトで定義されていますか？もしそうなら、あなたはあなたのペアのリストを単一のパスを使用してこれを行うことができます。

1）2つの「オブジェクト」パラメーターでインデックス付けされたバッグの空のコレクションを作成します。慣習により、最初のインデックスパラメーターは2番目のインデックスパラメーターよりも少ない必要があります。

2）リストをループして、Min（Pair.Left、Pair.right）で適切なバッグインデックスを見つけます。そのバッグに要素を追加します。

Answer 2

派手な用語は、この問題を困難にするかもしれませんが、実際には非常に簡単です。

1. 各ペアの要素を注文します。 （オブジェクトは数字として表すことができると言ったので、仮定しましょう pair.first <= pair.second いつも）
2. リストを並べ替えて、従来の方法を使用してペアを比較します。すなわち pair1 < pair2 意味 pair1.first < pair2.first また pair1.first == pair2.first && pair1.second < pair2.second.

例からソートされたリストは次のようになります

O1-P1-O2
O1-P4-O2
O1-P5-O2
O1-P3-O5
O1-P6-O5
O3-P2-O4
O7-P7-O8

これで、1つの「バッグ」のすべての要素がリスト内の連続したスポットを占有します。先に進み、それらをつかみます。

ハッシュでこれを解決するオプションもあります。

Answer 3

@nikita Rybakのソリューション Pythonを使用して itertools.groupby（）:

#!/usr/bin/env python
from itertools import groupby

pairs = """
O1-P1-O2
O3-P2-O4
O5-P3-O1
O1-P4-O2
O2-P5-O1
O1-P6-O5
O7-P7-O8
""".split()

def lex_order(pair):
    """'O2-P5-O1' -> ['01', '02']"""
    return sorted(pair.split('-')[::2])

data = sorted(pairs, key=lex_order)
for key, group in groupby(data, key=lex_order):
    print "key=%(key)s, pairs=%(pairs)s" % dict(key=key, pairs=list(group))

出力：

key=['O1', 'O2'], pairs=['O1-P1-O2', 'O1-P4-O2', 'O2-P5-O1']
key=['O1', 'O5'], pairs=['O5-P3-O1', 'O1-P6-O5']
key=['O3', 'O4'], pairs=['O3-P2-O4']
key=['O7', 'O8'], pairs=['O7-P7-O8']

@mbeckishのソリューション Python：

#!/usr/bin/env python
from collections import defaultdict

pairs = """
O1-P1-O2
O3-P2-O4
O5-P3-O1
O1-P4-O2
O2-P5-O1
O1-P6-O5
O7-P7-O8
""".split()

bags = defaultdict(list)
for pair in pairs:
    i, _, j = pair.split('-') # 'O2-P5-O1' -> ['02', 'P5', '01']
    bags[min(i,j), max(i,j)].append(pair)

import pprint;
pprint.pprint(dict(bags))

出力：

{('O1', 'O2'): ['O1-P1-O2', 'O1-P4-O2', 'O2-P5-O1'],
 ('O1', 'O5'): ['O5-P3-O1', 'O1-P6-O5'],
 ('O3', 'O4'): ['O3-P2-O4'],
 ('O7', 'O8'): ['O7-P7-O8']}