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

Question

У меня есть список пар объектов. Объекты могут появляться в паре в любом порядке. Какой наиболее эффективный алгоритм (и реализация?), Чтобы найти все сумки (т.е. наборы с разрешеной разрешенными) пар между теми же объектами. Для моей цели можно предположить, что ссылки на объект являются указателями, или именами или некоторыми подобными удобными, коротким, полезным представлением. Отдельные пары идентифицируются. Нет пар, которые имеют одинаковый объект в обеих частях пары.

Таким образом, учитывая список пар (OID является ссылкой на объект; ссылка на пари)

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) Создайте пустую коллекцию сумок, проиндексированную двумя параметрами «объекта». По соглашению, первый параметр индекса должен быть меньше, чем второй параметр индекса.

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

Answer 2

Причудливая терминология может усложнить эту проблему, но на самом деле это довольно просто.

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 3

Решение @nikita Rybak в питоне с использованием 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']}