Каков эффективный алгоритм извлечения сумок из списков пар?

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

Теперь все элементы из одной 'сумки' будут заниматьпоследовательные места в списке.Идите и возьмите их.

Есть варианты решения этой проблемы с помощью хэша.

Answer 2

Определено ли "меньше чем" на ваших объектах?Если это так, то вы можете сделать это за один проход по списку пар.

1) Создать пустую коллекцию сумок, проиндексированных двумя «объектными» параметрами.По соглашению, первый индексный параметр должен быть меньше, чем второй индексный параметр.

2) Перебрать список и найти соответствующий индекс сумки: min (pair.left, pair.right), max (pairслева, пара справа)Добавьте элемент в эту сумку.

Answer 3

@ решение Никиты Рыбака в 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's решение в 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']}