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.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

现在，一个“袋子”中的所有元素都将占据列表中的连续位置。来吧，抓住他们。

也有使用哈希解决这个问题的选项。

于 2010-10-21T18:42:19.150 回答
3

您的对象是否定义了“小于”？如果是这样，那么您可以通过单次遍历您的配对列表来执行此操作。

1）创建一个空的包集合，由两个“对象”参数索引。按照惯例，第一个索引参数应该小于第二个索引参数。

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 回答