Che cosa è un algoritmo efficiente per estrarre i sacchetti dalle liste di coppie?

Question

Ho una lista di coppie di oggetti. Gli oggetti possono apparire nella coppia in qualsiasi ordine. Qual è l'algoritmo più efficiente (e l'attuazione?) Per trovare tutte le borse (cioè insiemi con i duplicati consentiti) di coppie fra gli stessi oggetti. Per il mio scopo, i riferimenti agli oggetti possono essere considerate puntatori o nomi o qualche simile comodo, insomma, rappresentazione utile. Le singole coppie sono identificabili. Non ci sono coppie che hanno lo stesso oggetto in entrambe le parti della coppia.

Così dato una lista di coppie (OID è un riferimento all'oggetto; Pid riferimento coppia)

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

dovrebbe restituire:

P1;P4;P5 and P3;P6

Answer 1

è "minore di" definita sui vostri oggetti? Se è così, allora si può fare questo con un unico passaggio attraverso la vostra lista di coppie.

1) Creare un insieme vuoto di sacchetti, indicizzati da due parametri "Oggetto". Per convenzione, il primo parametro indice dovrebbe essere minore del secondo parametro index.

2) Loop attraverso la lista, e trovare l'indice di borsa appropriata al min (pair.left, pair.right), max (pair.left, pair.right). Aggiungere l'elemento a quella borsa.

Answer 2

Fancy terminologia può rendere questo aspetto problema difficile, ma in realtà è abbastanza semplice.

1. elementi d'ordine in ogni coppia. (Dal momento che detti oggetti possono essere rappresentati come numeri, supponiamo pair.first <= pair.second sempre)
2. Elenco Ordina, con metodo tradizionale per confrontare coppie. Cioè mezzi pair1 < pair2 pair1.first < pair2.first o pair1.first == pair2.first && pair1.second < pair2.second.

lista ordinata dal vostro esempio sarà simile a questa

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

Ora tutti gli elementi da una 'borsa' occuperà punti consecutivi nella lista. Andare avanti e afferrare.

Ci sono opzioni per risolvere questo con hash troppo.

Answer 3

@ la soluzione di Nikita Rybak in Python utilizzando 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))

Output:

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

@ La soluzione di mbeckish in 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))

Output:

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