Algorithmus zum Sortieren einer Liste basierend auf der Reihenfolge einer anderen, partiellen Liste

Question

Diese Frage unterscheidet sich von anderen Fragen zum Thema Sortieren einer Liste basierend auf der Reihenfolge einer anderen Liste in dem Sinne, dass die Bestellliste nicht alle enthält die in der Liste verwendeten Schlüssel.

Angenommen, ich habe eine Liste [a, b, c, d, e] und meine Bestellliste [b, d, e].

Jetzt ändere ich meine Bestellliste zu [b, e, d]. Gibt es einen relativ einfachen Algorithmus, um die ursprüngliche Liste wiederherzustellen? Nehmen wir an, es ist nicht wichtig, ob die letzte Bestellung [a, b, e, c, d] oder [a, b, c, e, d] ist, und die Bestellliste wird immer eine Teilmenge der ursprünglichen Liste sein.

Edit: einige Fragen über die endgültige Bestellung Aufräumen, von meinem Beispiel: e bestellt wurde zwischen b und d, und in der sortierten Liste sein, es ist egal, ob e-b oder d benachbarte landet. Aber zum Beispiel, wenn aufgrund dieser Sortierung a nach b bewegt - während eine rechtliche Bestellung - es ist nicht wünschenswert.

Answer 1

BEARBEITEN Hier ist eine etwas effizientere Version; anstatt den Index der Ordnungselemente in jeder Iteration (arr.IndexOf) nachzuschlagen, schauen Sie einfach einmal am Anfang nach, um die Indizes zu aktualisieren.

schlimmste Zeit, wenn N die Länge des Arrays ist und M die Länge der Ordnung O (N * M + M^2)

function partialSort(arr, order) { 
    var orderIndex = []; 
    for(var i = 0; i < order.length; i++) { 
     orderIndex[i] = arr.indexOf(order[i]); 
    } 
    for(var i = 0; i < orderIndex.length; i++) { 
     var indexI = orderIndex[i]; 
     for(var j = i + 1; j < orderIndex.length; j++) { 
      var indexJ = orderIndex[j]; 
      if(indexI > indexJ) { 
       var temp = arr[indexI]; 
       arr[indexI] = arr[indexJ]; 
       arr[indexJ] = temp; 
       orderIndex[i] = indexJ; 
       orderIndex[j] = indexI; 
       indexI = indexJ; 
      } 
     } 
    } 
    return arr; 
} 
var a = [1, 2, 3, 4, 5, 6, 7]; 
var o = [3,5,7]; 
console.log(o + "\n" + partialSort(a, o)); 
o = [5,3,7]; 
console.log(o + "\n" + partialSort(a, o)); 
o = [7,3,5]; 
console.log(o + "\n" + partialSort(a, o)); 

---

ist

Hier ist die Version mit einem MlogM sortieren O (N * M + M * log (M) + M)

function partialSort(arr, order) { 
    var orderIndex = []; 
    for(var i = 0; i < order.length; i++) { 
     orderIndex[i] = arr.indexOf(order[i]); 
    } 
    // sort by index ~some quick sort variant O(M * log(M)) 
    orderIndex.sort(function(a, b) { return a - b; }); 
    // put the ordered elements in the correct sequence in the main array 
    for(var i = 0; i < orderIndex.length; i++) { 
     arr[orderIndex[i]] = order[i]; 
    } 
    return arr; 
} 

Wenn Sie die absolut beste Effizienz Sie orderIndex.sort mit einem Radixsort O (N * M + M + M)

Answer 2

Ein naiver n^2 Ansatz:

for each S in order-list 
    if S is in other-list 
    remove S from other-list 
    add S to end of other-list 

, die in den Elementen aus Ihrer Art-Liste wird entfernt und die beigefügte auf Ihre andere Liste führen: [a, c, b, e, d]

Answer 3

Python Ansatz, einfach implementiert in jede Sprache (Java wird nicht functools erforderlich)

import functools 

order = [5, 1, 4] 

def numeric_compare(x, y): 
    if x in order and y in order: 
     if order.index(x) > order.index(y): 
      return 1 
     elif order.index(x) < order.index(y): 
      return -1 
    else: 
     if x in order: 
      return -1 
     elif y in order: 
      return 1 
    return 0 

a = [1,2,3,4,5] 
a.sort(key = functools.cmp_to_key(numeric_compare)) 

Answer 4

Sie erreichen, was Sie wollen, indem Sie eine benutzerdefinierte Komparator Einrichtung als Dennis Callanan hat sugg ested und dann eine stabile Art des Arrays zu tun. Quicksort ist keine stabile Sorte; Es wird im Allgemeinen die Reihenfolge der Elemente ändern, die nicht in der Teilordnung enthalten sind. Merge sort ist eine stabile Sortierung.

Wenn Sie lineare Suche im Komparator verwenden, wird der Algorithmus in der Zeit laufen O (n^2 log n) denke ich. Was Sie tun müssen, um es schneller laufen zu lassen, besteht darin, einen Durchlauf durch das neue Array zu machen, indem Sie die Position jedes Elements im Array für schnelle Suchvorgänge hashen.

Ich könnte es in Java implementieren, aber ich weiß nicht Python, sorry.

Eine andere Perspektive ist eine topologische Sortierung. In Ihrer ursprünglichen Liste hatten Sie ein -> b -> c -> d -> e, wobei die Pfeile ein "kommt vor" b bedeuten. Dann fügen Sie die neuen Daten b -> e -> d hinzu. Sie müssen alle Pfeile in der ersten Liste brechen, die zu Widersprüchen führen, d. H. D -> e. Was Sie dann haben, ist ein Bündel Pfeile:

a -> b, b -> c, c -> d, b -> e, e -> d

Wenn das ein gerichteter azyklischer Graph (dh keine Widersprüche), können Sie dann toposort es in O (V + E) Zeit. Da die Anzahl der Kanten höchstens 2n beträgt, ist dies O (n) Zeit, sehr effizient.

Das Problem ist zu entscheiden, welche Pfeile in der ursprünglichen Liste zu brechen (und vielleicht durch andere Pfeile ersetzen), so dass es keine Widersprüche gibt. Im Allgemeinen ist das ein NP-schweres Problem, das minimum feedback arc set genannt wird, aber ich vermute, dass es etwas in der Struktur Ihres Problems gibt, das es schneller laufen lassen würde.

Schließlich, was ist nur mit dem Ersetzen der Elemente im (nicht zusammenhängenden) Subarray [..., b, ..., d, e] mit der Permutation durch das neue Array gegeben? Das kann in O (n) Zeit erreicht werden.

Answer 5

ersetzen könnte

Ich schrieb eine Version von Quicksort zum Spaß für eine andere Frage (Javascript Double sorting algorithm), die ich nicht weiß, ob es absolut zuverlässig ist. Es war ursprünglich nur die Saiten zu sortieren gemeint oder die Zahlen nur scheint aber anpassungsfähig auf diesen Fall (Ich habe die „ISNUMBER“ und „weniger“ Funktionen):

function isNumber(x,y) { 
    return (map[x]); 
} 

function less(a,b,y){ 
    return y ? a < b : map[a] < map[b]; 
} 

function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } 

function partition(array, pivot, left, right, what) { 
    var store = left, 
     pivotValue = array[pivot]; 

    swap(array, pivot, right); 

    for (var v = left; v < right; v++) { 
    if (less(array[v],pivotValue,what) && isNumber(array[v],what)) { 
     swap(array, v, store); 
     store++; 
    } 
    } 

    while(!isNumber(array[store],what)) 
    store++; 

    swap(array, right, store); 

    return store; 
} 

function doubleQSort(array, left, right, what) { 
    while(!isNumber(array[right],what) && right > left) 
    right--; 
    while(!isNumber(array[left],what) && left < right) 
    left++; 

    var pivot = null; 

    if (left < right) { 
    pivot = (right + left) >> 1; 

    while(!isNumber(array[pivot],what)) 
     pivot--; 

    newPivot = partition(array, pivot, left, right, what); 

    doubleQSort(array, left, newPivot - 1,what); 
    doubleQSort(array, newPivot + 1, right,what); 
    } 
} 

Ausgang:

var things = ['a', 'b', 'c', 'd', 'e']; 
var map = {'b':1, 'e':2, 'd':3} 

doubleQSort(things,0,things.length - 1); 
console.log(things) // [a, b, c, e, d]