3

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

ペアのリストが与えられた場合 (Oid はオブジェクト参照、Pid はペア参照)

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
4

3 に答える 3

5

派手な用語を使うと、この問題が難しく見えるかもしれませんが、実際には非常に単純です。

  1. 各ペアの要素を並べ替えます。（オブジェクトは数値として表現できると言ったので、pair.first <= pair.second常に仮定しましょう）
  2. ペアを比較する従来の方法を使用して、リストを並べ替えます。つまり、 またはpair1 < pair2を意味します。pair1.first < pair2.firstpair1.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 つの「バッグ」のすべての要素が、リスト内の連続した場所を占有します。先に進み、それらをつかみます。

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

于 2010-10-21T18:42:19.150 に答える
3

オブジェクトで「未満」が定義されていますか? その場合は、ペアのリストを 1 回通過するだけでこれを行うことができます。

1) 2 つの「オブジェクト」パラメーターによってインデックス付けされたバッグの空のコレクションを作成します。慣例により、最初のインデックス パラメータは 2 番目のインデックス パラメータより小さくする必要があります。

2) リストをループし、min(pair.left,pair.right), max(pair.left, pair.right) で適切なバッグ インデックスを見つけます。そのバッグに要素を追加します。

于 2010-10-21T18:45:42.963 に答える
1

@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']}
于 2010-10-21T19:53:49.000 に答える