Unione di alcune liste ordinate con sequenza ordini sconosciuta

Question

Ho alcune liste con numero variabile di elementi. Ogni lista è ordinata, ma l'algoritmo di ordinamento non è noto. Vorrei unire le liste in un'unica grande lista che contiene tutte le liste nello stesso ordine, senza duplicati.

Esempio Ingresso:

1. XS, M, L, XL
2. S, M, XXL
3. XXS, XS, S, L

Risultato previsto:

• XXS, XS, S, M, L, XL, XXL

Il risultato atteso è ottenuto facendo corrispondere le sequenze di input per ottenere un risultato unito contenente gli elementi di ogni sequenza di ingresso nell'ordine corretto, come questo:

XS M L XL 
     S M  XXL 
XXS XS S L 
------------------- 
XXS XS S M L XL XXL 

La funzione dovrebbe notificare, se ci sono elementi che hanno posizioni ambigue. Qui, sarebbe XXL (potrebbe rimanere dopo M, L o XL) e ho bisogno di specificare la sua posizione manualmente dopo XL (perché qui conosco l'algoritmo di ordinamento e può aiutare). Ho pensato di definire coppie di ogni due elementi, ogni coppia in ordine come nella lista originale. Da questo si potrebbe costruire l'elenco completo.

Answer 1

Ecco cosa farei:

1. preprocess liste: capire che XXS è più piccolo di XS è più piccolo di S è più piccolo di ... XXL è un [problema di soddisfacimento di vincoli] (http://en.wikipedia.org/wiki/Constraint_satisfaction_problem). Questo tipo di problema comporta la ricerca di un ordine corretto tra tutti gli elementi dati i vincoli definiti negli elenchi originali.
2. Creare un mapping bidirezionale dall'insieme {XXS, ..., XXL} all'insieme {1, ..., 6}, dopo aver completato il passaggio 1.
3. Per ogni elenco, creare un altro elenco da utilizzando il mapping definito in 2.
4. Utilizzare un [unisci sort] modificato (http://en.wikipedia.org/wiki/Merge_sort) per combinare due elenchi. Modificare l'algoritmo di fusione in modo che venga segnalato se due elementi confrontati sono identici (e ignora uno degli elementi da unire).
5. Eseguire il passaggio 4 per ciascuna coppia di elenchi finché non è disponibile una lista.
6. Utilizzando la mappatura definita in 2, creare la versione di testo dell'elenco.

Answer 2

Questo può essere risolto con una Topological Sort algoritmo.

Se si considera ciascuna delle sequenze di input per essere un percorso attraverso un grafo orientato, una sorta topologico ordinerà il set di nodi da sinistra a destra in modo tale che ogni punto arco orientato verso destra.

pagina di Wikipedia su Topological Sorting include questo algoritmo, in primo luogo descritto da Arthur Kahn nel 1962:

L ← Empty list that will contain the sorted elements 
S ← Set of all nodes with no incoming edges 
while S is non-empty do 
    remove a node n from S 
    insert n into L 
    for each node m with an edge e from n to m do 
     remove edge e from the graph 
     if m has no other incoming edges then 
      insert m into S 
if graph has edges then 
    return error (graph has at least one cycle) 
else 
    return L (a topologically sorted order) 

Questo algoritmo, come scritto, in realtà non fallire se trova sequenze ambigue, ma che è facile per aggiungere inserendo un controllo all'inizio del ciclo, in questo modo:

... 
while S is non-empty do 
    if S contains more than 1 item 
     return error (inputs are ambiguous) 
    remove a node n from S 
    ... 

non so che lingua si sta lavorando, ma ho buttato insieme questa implementazione PHP come prova di concetto:

function mergeSequences($sequences, $detectAmbiguity = false) { 

    // build a list of nodes, with each node recording a list of all incoming edges 
    $nodes = array(); 
    foreach ($sequences as $seq) { 
     foreach ($seq as $i => $item) { 
      if (!isset($nodes[$item])) $nodes[$item] = array(); 
      if ($i !== 0) { 
       $nodes[$item][] = $seq[$i-1]; 
      } 
     } 
    } 

    // build a list of all nodes with no incoming edges 
    $avail = array(); 
    foreach ($nodes as $item => $edges) { 
     if (count($edges) == 0) { 
      $avail[] = $item; 
      unset($nodes[$item]); 
     } 
    } 

    $sorted = array(); 
    $curr = '(start)'; 
    while (count($avail) > 0) { 

     // optional: check for ambiguous sequence 
     if ($detectAmbiguity && count($avail) > 1) { 
      throw new Exception("Ambiguous sequence: {$curr} can be followed by " . join(' or ', $avail)); 
     } 

     // get the next item and add it to the sorted list 
     $curr = array_pop($avail); 
     $sorted[] = $curr; 

     // remove all edges from the currently selected items to all others 
     foreach ($nodes as $item => $edges) { 
      $nodes[$item] = array_diff($edges, array($curr));     
      if (count($nodes[$item]) == 0) { 
       $avail[] = $item; 
       unset($nodes[$item]); 
      } 
     } 

    } 

    if (count($nodes) > 0) { 
     throw new Exception('Sequences contain conflicting information. Cannot continue after: ' . join(', ', $sorted)); 
    } 

    return $sorted; 
} 

è possibile chiamare la funzione come questa:

$input = array(
    array('XS', 'M', 'L', 'XL'), 
    array('S', 'M', 'XXL'), 
    array('XXS', 'XS', 'S', 'L'), 
); 
echo(join(', ', mergeSequences($input))); 
echo(join(', ', mergeSequences($input, true))); 

Per ottenere il seguente risultato:

XXS, XS, S, M, XXL, L, XL 
Uncaught exception 'Exception' with message 'Ambiguous sequence: M can be followed by L or XXL' 

Answer 3

Si sta tentando di unire partially ordered sets o posets. Le parti ambigue dell'unione sono chiamate antichains. Quindi, vuoi un algoritmo che unisce i poset e ti dice quali sono gli antichain.

Here is a paper describing an algorithm for merging posets and detecting antichains, così come un link to the first author's homepage nel caso in cui si desidera contattarlo per vedere se c'è qualche codice sorgente disponibile.

Answer 4

Per la parte di ordinamento, penso che Merge Sort è sufficiente in base alla descrizione. Una cosa è necessario modificare durante l'unione, dovremmo saltare gli elementi nell'array di input se il primo elemento dell'array di input è lo stesso dell'array di risultati.

Se ho capito bene, vuoi costruire un ordine totale di tutti gli elementi di input possibili. Alcuni ordini parziali sono già definiti negli array di input (poiché sono già ordinati), mentre altri devono essere specificati dagli utenti. Ad esempio in questione, dell'ordine

'S' < 'M' < 'XXL'

'XS' < 'M' < 'L' < 'XL'

'XXS' < ' XS '<' S '<' L '

è ben definito. Ma l'algoritmo non sa ancora se 'XXL' è più grande o più piccolo di 'XL', 'L'.
Poiché i tre array di input sono ordinati, deve esistere un ordine totale degli elementi di input. Quindi il mio suggerimento è di chiedere al vostro fornitore di dati un elenco ordinato di tutti i possibili elementi di dati. Sembra stupido, ma è un modo semplice.

Se questo elenco non è disponibile, un modo semplice per trattare è richiedere un ordinamento di coppie per l'utente, quindi controllare se questo è in conflitto con la sequenza di input esistente e ricordarlo, quando l'algoritmo incontra una coppia ambigua. Penso che l'ordinamento della topologia sia più potente di questa applicazione. Dato che trattiamo con singoli elementi di dati, è necessario uscire da un ordine totale. Mentre l'ordinamento della topologia deve occuparsi dell'ordine parziale.