从一组配对列表中提取袋子的有效算法是什么？

Question

我有一组对象对的列表。对象可以以任意顺序出现在对中。如何找到所有由相同对象之间的对组成的包（即允许重复的集合）的最有效算法（和实现）？对于我的目的，可以假设对象引用是指针、名称或某种类似方便、短小、有用的表示。各个对是可识别的，没有两部分都是同一个对象的对。

因此，给定一组对的列表（Oid 是对象引用；Pid 是对的引用）。

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

should return:

P1;P4;P5 and P3;P6

- Chris Walton

---

你尝试过什么？一个简单的字典/哈希直方图（支持数组）或者一个多重映射都可以正常工作。只需始终使用稳定有序对进行索引。 - user166390

我认为这取决于实现的限制。如果我们处理的是字符串，而不是可以直接访问三个组件的对象，则情况就不同了。理想情况下，您应该将对象规范化，以便可以对列表进行排序（例如，如果最低值对象首先出现），然后从那里开始。 - Jamie Treworgy

我在这个问题中强调了效率，因为检查袋子的工作必须在一个内部循环中完成；必须在大型列表上进行检查；而且需要检查的列表部分会经常发生变化。 - Chris Walton

这是我希望能够接受多个答案的场合之一。所有的答案都非常有用，而且非常有帮助、相关和发人深省。谢谢。 - Chris Walton

Answer 1

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

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

现在，来自一个“包”中的所有元素将占据列表中连续的位置。继续并获取它们。

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

- Nikita Rybak

---

谢谢你提供这个。你的方法难道不涉及至少三次数据通行吗？如果是这样，那么它的效率可能不如我所期望的高 - 请看我的关于效率的评论。 - Chris Walton

@Chris 哈希表。这会给你一个线性解决方案，并且如果仔细实现，只会稍微增加内存消耗。 - Nikita Rybak

我已经在Python中实现了你的答案。https://dev59.com/mlHTa4cB1Zd3GeqPQVB3#3991352 - jfs

Answer 2

你的对象是否定义了“小于”操作符？如果是，那么你可以通过一次遍历你的键值对列表来完成这个操作。

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

2) 循环遍历列表，找到最小(pair.left, pair.right)和最大(pair.left, pair.right)的适当的袋子索引。将元素添加到该袋子中。

- mbeckish

---

我的对象目前没有少于定义的，但这是一个非常容易融入的细节。这似乎是我正在寻找的方法，只涉及一次数据遍历。我会更详细地研究这个问题。考虑到大列表中的一小部分将快速更改，但对我所要做的事情最感兴趣，是否有更有效的方法来处理这个问题？ - Chris Walton

如果你将一个 List 中的 N 个元素复制到一组 Bags 集合中，那么运行时间至少为 O(N)。 - mbeckish

谢谢。在注释之间，我意识到采用您的方法可以提高效率，但是预先计算袋子的集合，并仅重复计算变化部分。仍然是O(n)，但n大大减少了。再次感谢。 - Chris Walton

我已经在Python中实现了你的答案。https://dev59.com/mlHTa4cB1Zd3GeqPQVB3#3991352 - jfs

Answer 3

使用 itertools.groupby() 和 Python，参考 Nikita Rybak的解决方案：

#!/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']

Python中的@mbeckish's solution:

#!/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']}

- jfs

---

我理解那个切片技巧的作用([::2])，但你能告诉我它的术语是什么吗？我想多了解一些。 - jlv

@jlv: "扩展切片": a[i:j:k] 选择所有满足条件 x = i + n*k, n >= 0 且 i <= x < j 的 a 中的元素。详见 http://docs.python.org/reference/datamodel.html 。如需进一步使用，请了解 __getitem__(), slice() 和 numpy 数组。 - jfs