Algoritma, kısmi, liste

Question

Bu soru sipariş listesi tüm içermemesi anlamda başka bir listenin sırasına göre bir liste sıralama konudaki diğer sorulara farklıdır listede kullanılan tuşlar.

Bir liste [a, b, c, d, e] ve sipariş listeme [b, d, e] olduğunu varsayalım.

Şimdi [b, e, d] benim sipariş listesini değiştirebilir. Orijinal listeye başvurmak için nispeten basit bir algoritma var mı? Son siparişin [a, b, e, c, d] veya [a, b, c, e, d] olup olmadığının önemli olmadığını ve sipariş listesinin her zaman orijinal listenin bir alt kümesi olacağını düşünelim.

Düzenleme: benim örnekten, nihai sipariş hakkında bazı sorular açılıyor: eb ve d arasında olması emredildi ve eb veya d bitişik biter eğer sıralı listede hiç önemli değil. Ancak örneğin, a numaralı bu sıralama nedeniyle b'dan sonra taşınmışsa - yasal bir sipariş verirken - bu arzu edilmez.

Answer 1

EDIT İşte biraz daha verimli bir sürüm; Her iterasyonda (arr.indexOf) düzen elemanlarının indeksini aramak yerine, indeksleri güncel tutmak için başlangıçta bir kez görünün.

kötü zaman K için Dizinin uzunluğu ve M sipariş uzunluğu ise O'dur (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)); 

---

Burada bir MlogM sort O (N * M + M * günlük (M) + M)

kullanarak sürüm bulunmaktadır.

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; 
} 

Eğer bir basamağa göre sıralama O (N * M + M + M)

Answer 2

Bir naif n^2 yaklaşımdır: En sıralama listesinden öğeleri sonuçlanacaktır

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

kaldırılır ve diğer listeye ekleniyor: [a, c, b, e, d]

Answer 3

Python yaklaşımı, kolayca uygulanan herhangi bir dil

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

Dennis Callanan SUGG olduğu gibi özel bir karşılaştırıcı kurarak istediğini başarabilirsiniz (Java functools gerektirmez) Tahmin edildikten sonra dizinin durağan bir sıralaması yapıyor. Quicksort kararlı bir sıralama değildir; Genellikle kısmi sıralamada yer almayan öğelerin sırasını değiştirecektir. Birleştirme sıralama, kararlı bir sıralamadır.

Eğer karşılaştırıcı lineer araması kullanıyorsanız, algoritma zaman O (n^2 günlük n) Bence çalışır. Daha hızlı çalışmasını sağlamak için yapmanız gereken şey, yeni diziden bir satırlık işlem yapmak ve hızlı arama yapmak için dizideki her öğenin konumunu sağlamlaştırmaktır.

Java uygulamak olabilir ama üzgünüm, Python bilmiyorum.

Bu konuda başka bir bakış açısı topolojik sıralama kullanmaktır. Orijinal listenizde -> b -> c -> d -> e öğeleriniz vardı ve burada oklar "önce gelir" derken b. Ardından yeni verileri b -> e -> d ekleyin. İlk listede çelişkilere yol açan herhangi bir ok kırmanız gerekir, yani d -> e. Ne sonra sahip oklar bir demet: -> B, B -> C, C -> D, B -> E, E -

bir bu ise> d

yönlendirilmiş bir asiklik grafiktir (olup Yani, çelişki yok), o zaman toposort O (V + E) zamanında yapabilirsiniz. Kenarların sayısı en fazla 2n olduğu için, bu O (n) zaman, çok verimli.

konu oklar kırmak (ve belki diğer oklarla değiştirin) herhangi çelişkiler var olmayacak şekilde orijinal listedeki ne karar vermektir. Genelde bu, minimum feedback arc set adı verilen bir NP-zor problemidir, ancak probleminizin yapısında daha hızlı çalışmasını sağlayacak bir şey olduğundan şüpheleniyorum.

Son olarak, (bitişik olmayan) alt dizideki [..., b, ..., d, e] öğelerini yeni dizinin verdiği izinle değiştirmek yerine ne dersiniz? Bu O (n) zamanında gerçekleştirilebilir.

Answer 5

ile orderIndex.sort yerini alabilecek mutlak iyi verimi istiyorsanız

Başka bir soru için (Javascript Double sorting algorithm), tamamen güvenilir olup olmadığına dair hiçbir fikrim olmadığı için bir eğlence mesajı hazırladım.

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); 
    } 
} 

Çıktı:

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]