从成对列表中提取包的有效算法是什么？

Question

我有一个对象对的列表。对象可以以任一顺序出现在对中。查找相同对象之间的所有对的包（即允许重复的集合）的最有效算法（和实现？）是什么。出于我的目的，对象引用可以被假定为指针、名称或一些类似的方便、简短、有用的表示。各个对是可识别的。不存在在该对的两个部分中具有相同对象的对。

因此，给定一个对列表（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

Answer 1

花哨的术语可能会让这个问题看起来很困难，但实际上非常简单。

1. 对每对中的元素进行排序。 （既然你说对象可以表示为数字，那么我们就假设总是pair.first <=pair.second）
2. 对列表进行排序，使用传统的方式来比较对。即pair1 < pair2 表示pair1.first < pair2.first 或 pair1.first ==pair2.first &&对1.第二个<对2.第二个。

示例中的排序列表将如下所示

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

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

也有一些选项可以使用哈希来解决这个问题。

Answer 2

您的对象上定义了“小于”吗？
如果是这样，那么您可以通过一次遍历配对列表来完成此操作。

1) 创建一个空的袋子集合，由两个“对象”参数索引。按照约定，第一个索引参数应小于第二个索引参数。

2) 循环遍历列表，并在 min(pair.left,pair.right), max(pair.left,pair.right) 处找到适当的包索引。将元素添加到该包中。

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']}