Unione di elenchi ordinati (senza funzione di confronto)

Questo è un problema ben definito con una soluzione deterministica. Puoi pensare a ciascuna lista come parte di un grafico aciclico diretto :

Quindi,lacostruzionediunordineunitoèsemplicementeunaquestionediutilizzodiunodeibennotialgoritmipertrovareun ordinamento topologico . Più somiglianze hai tra le liste, meno pochi tipi topologici validi avrai. Se non ci sono elementi in comune, l'ordinamento topologico funzionerà anche per quel caso. Elencherà tutti i modi possibili per combinare le tre liste. Devi solo scegliere quello che ti sta meglio esteticamente.

Se non hai letteralmente nessuna funzione di confronto, allora l'unica opzione ragionevole è quella di scegliere lo stesso ordine ogni volta:

one = [1,2,3]
two = [4,5,6]
three = [7,8,9]

merge(one, two, three) == [1,4,7,2,5,8,3,6,9]

Se c'è un ordine e gli oggetti possono essere confrontati per l'uguaglianza, ma non puoi codificare l'ordine in modo esplicito, puoi tenere traccia di quante volte li hai visti in determinati ordini e usarli per generare euristiche.

Puoi creare una cronologia su cui basare le ipotesi memorizzando tutte le visite

Penso che questi tipi di dati e algebra (espressi in pseudo-scala) servano bene a questo scopo.

// How many times a given item has been seen
type ItemCount = Map[Item, Int]

// NB ItemHistory forms a commutative monoid with zero as empty maps and mappend adding the counts together
case class ItemHistory(itemsSeenBefore: ItemCount, itemsSeenAfter: ItemCount)

// Fold over a list of input items and generate history for each one, storing the count of all items seen before and after
List[Item] => Map[Item, ItemHistory]

// Update your counts with more data
(Map[Item, ItemHistory], List[Item) => Map[Item, ItemHistory]

// Generate an ordering between two items, with a % accuracy.
// Whichever has been seen more often before or after defines the ordering.
// The accuracy is determined by taking the ratio of times that ordering was correct vs the entire history.
(Item, ItemHistory) => (Item, ItemHistory) => (Ordering, Float)

// Apply some cutoff for filtering out inaccurate orderings
(Ordering, Float) => Ordering

Se implementi una classe con metodi lungo quelle linee, puoi usarla per generare euristiche. Poiché ItemHistory è un monoid, puoi facilmente addestrarlo offline con i dati che hai oggi, persistere in ItemHistories in qualsiasi modo conveniente, e quindi aggiornarli continuamente con i nuovi dati di allenamento appena entrati.