Un algoritmo per trovare duplicati inversi di coppie ordinate

Question

Un algoritmo per trovare duplicati inversi di coppie ordinate

#1 da (1 voti)
#2 da (-2 voti)
#3 da (-2 voti)
#4 da (-2 voti)

1

Data una serie di coppie di valori ordinati, quale algoritmo troverà i duplicati inversi? [Converse significa gli stessi valori, ma nell'ordine opposto.]

Cioè, dato [ab, ac, ad, bc, bd, ca, db] c'è un modo efficiente per trovare ca e db, essendo i duplicati inversi per ac e bd?

L'applicazione è abbastanza semplice: le coppie ordinate sono spigoli in un grafico diretto e se c'è un bordo opposto allora si deve disegnare un singolo fronte doppio anziché un bordo in ogni direzione. I valori sono stringhe, essendo nomi di nodi.

Può essere visto come una ricerca in una matrice sparsa. Date le coordinate (a, b), controllate se (b, a) esiste. Tuttavia, i linguaggi di programmazione comuni non forniscono (sembrano) array sparsi di 2d.

Ho scritto una soluzione in ruby usando hash-of-hash, ma sono circa 20 righe di codice scomodo e un risultato insoddisfacente. Scrivere lo stesso codice in una lingua come C # o Java sarebbe più lungo. Si cerca una soluzione migliore, in pseudocodice o una descrizione (passaggi) dell'algoritmo. Ad ogni modo, sto cercando una risposta che descriva come trovare la soluzione, nonché i vantaggi e gli svantaggi dell'algoritmo specifico.

Non ho tentato di definire "efficiente" o "migliore" e le prestazioni non sono una considerazione prioritaria per un disegno di poche centinaia di nodi.

I nodi non sono ordinati, quindi l'algoritmo predefinito sarebbe, per ogni coppia, per formare la ricerca inversa e forza bruta nella metà precedente. Una ricerca binaria richiederebbe un ordinamento precedente. Una soluzione basata sull'indicizzazione hash dovrebbe essere molto più veloce.

algorithms graph

posta david.pfx 02.07.2014 - 09:34

fonte

4 risposte

Leggi altre domande sui tag algorithms graph

L'implementazione fisica dell'algoritmo di ricottura quantistica I nomi di variabili vaghe sono più mantenibili?

score 1 · Answer 1

Raccogli le coppie in un set. (In Ruby, sarà un Set di Array a due elementi.)

let Set s = {}
for each pair [a,b]
   if s contains [a,b]
      // duplicate, do nothing
   else if s contains [b,a] // converse duplicate
      ...
   else
      add [a,b] to S

Se stai scrivendo Ruby, è già in grado di utilizzare gli array

score -2 · Answer 2

Questo è il codice per la mia implementazione di ruby. L'output è in un formato destinato a Graphviz.

  graph_edges = {}
  fmap.keys.sort.each do |srckey|
    forms = fmap[srckey]
    fsrc = $1 if srckey =~ /---/
    forms.keys.each do |fkey|
      fdest = $1 if fkey =~ /---/
      if fdest
        if graph_edges[fdest] && graph_edges[fdest][fsrc]
          graph_edges[fdest][fsrc] = :both
        else
          graph_edges[fsrc] ||= {}
          graph_edges[fsrc][fdest] ||= :only
        end
      end
    end if fsrc
  end
  fout3.puts "digraph {"
  graph_edges.each do |fsrc,h| 
    h.each_pair do |fdest,dir| 
      dirs = " [dir = both]" if dir == :both
      fout3.puts "  #{fsrc} -> #{fdest}#{dirs};" 
    end
  end
  fout3.puts "}"

Speriamo che ci sia qualcosa di utile qui. Lavorerò su qualcosa di meglio basato su un hash del valore della tupla.

score -2 · Answer 3

Ecco una soluzione funzionante con prestazioni decenti.

ordered = lambda x, y: (x, y) if x <= y else (y, x)

def makeArrows(edges):
  """
  input: a sequence of (src, dst) pairs, maybe some reciprocal.
  output: generator yielding (src, dst, is_double_ended) triples.
  """
  undirected_edges = set()
  for src, dst in edges:
    edge = ordered(src, dst)  # both 'ab' and 'ba' become ('a', 'b') here
    if edge in undirected_edges:
      # we found a reciprocal; there can only be one pair like 'ab' + 'ba',
      # so we remove it and output as double-ended
      undirected_edges.remove(edge)
      yield (src, dst, True)
    else:
      # accumulate an edge and wait; a reciprocal might be ahead
      undirected_edges.add(edge)
  # all edges not removed by now are one-ended
  for (src, dst) in undirected_edges:
    yield (src, dst, False)

Ora possiamo provarlo. Poiché le stringhe Python sono sequenze, qui ho selezionato 'ab' anziché ('a', 'b') .

raw_edges = ['ab', 'ac', 'ad', 'bc', 'bd', 'ca', 'db']

>>> list(makeArrows(raw_edges))
[('c', 'a', True), ('d', 'b', True), ('b', 'c', False), ('a', 'b', False), ('a', 'd', False)]

score -2 · Answer 4

Ecco un modo ... in python

ordered = lambda x, y: (x, y) if x <= y else (y, x)

def make_hash(edges):
    edge_hash = {}
    for x,y in edges:
        edge = ordered(x, y)
        edge_hash[edge] = edge_hash.setdefault(edge, 0) + 1
    return edge_hash

edges = ['ab', 'ac', 'ad', 'bc', 'bd', 'ca', 'db']

for edge, count in make_hash(edges).items():
    print ''.join(edge), 'uni' if count == 1 else 'bi'

Crea un dizionario (cancelletto) che viene indicizzato dall'ordine ordinato dei bordi. Se ci sono due voci, sappiamo che ha un duplicato inverso. Se solo uno, non lo è. Il dizionario viene restituito e il conteggio delle voci corrispondenti (in qualsiasi ordine).