Reduzieren Permutation

Question

Ich brauche einen Algorithmus, kann die Karte die läuft in einer permutation zu einer einzigen Zahl, sondern verringern auch den nachfolgenden zahlen.

So ein Lauf ist eine fortlaufende Reihe von zahlen in einer permutation, die sortiert und in Ordnung.In der Liste, 1;2;3;5;6;4 es gibt zwei Läufe, 1;2;3 und 5;6.Ich will ersetzen Sie diese durch eine einzelne Zahl, ein minimum, so dass, wenn, nach dem entfernen läuft, haben wir eine permutation der 4 Elemente, die permutation verwendet die zahlen 1 ...4.In der oben genannten, wir haben zu reduzieren die beiden läuft.der erste Lauf wäre 1, 4 verwandelt, um 2, und [5;6] verwandelt zu 3, zu halten das zweite Kriterium.Wenn ich die Sortierung der reduzierten permutation, dann erweitern Sie die Elemente innerhalb von mapping und Sortieren Sie die ursprüngliche permutation ich das gleiche Ergebnis erhalten.Die daraus resultierende permutation sollte nicht jeder läuft in es.

Zum Beispiel (ich habe hervorgehoben, die ausgeführt wird):

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

für jetzt, ich bin überfahren der Liste und eine Liste der Listen der Gruppierung ausgeführt wird.Wirklich der zweite Teil ist schwer zu machen eine saubere Lösung.Ich dachte daran, wie der naive Ansatz, neugierig, ob jemand hat einen cleveren trick, der es besser machen können, die dann von mir, ich bin wie O( 2n + n log n),

• austauschen der läuft mit dem head-element der Lauf und das einfügen dieser Daten in einer Hash-Tabelle (für die Wiederherstellbarkeit)
• Sortieren, um eine Karte zu erstellen, um die fehlenden Ziffern mit sortierten index.[1;6;5;4] ausgeben würde [(1,1);(4,2);(5,3);(6,4)]
• austauschen der Liste in Schritt 1 mit der map erstellt in Schritt 2 und Aktualisierung der hashtable für die übersetzung.

laufen Sie durch ein Beispiel, wieder:

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

Wenn ich Sortieren diese permutation und rekonstruieren:[1;2;3;4], 3->3;4 und 4->5;6 ich bekommen, 1;2;3;4;5;6.Auch sortiert.

Ich bin mit Listen, also einen funktionalen Ansatz bevorzugt.Kein code notwendig.Alle Ideen natürlich willkommen.

EDIT:

mweerden:

Es ist mir nicht klar, was die genauen Bedingungen, auf die das mapping.Warum genau ist es nicht erlaubt, nur produzieren die permutation [1,2,...,N] eine beliebige permutation der N läuft?Sie scheinen zu bevorzugen, um eine Zuordnung ausführen, um eine Nummer aus, die ausgeführt werden können, aber (dies ist nicht immer möglich), die Sie zu erlauben scheinen einige Freiheit.–

Ich glaube nicht, lieber eine Karte führen zu einer Zahl innerhalb-Lauf (oben schauen!), aber ich muss bewahren Sie ein Bestellung.Die permutation [1;2;3...N] ist eine Flucht, und kann so weiter reduziert werden.Deshalb ist es ungültig.Die Reihenfolge ist egal, in weitere Operationen in anderen Algorithmus, aber die einzelnen Elemente können erweitert werden, am Ende retten die ursprüngliche permutation.

Answer 1

Notation:

• Zählung beginnt bei 1
• l.i ist element i Liste l
• l+m ist die Verkettung von Listen l und m
• ein Lauf ist eine maximale Teilliste ist eine Liste [n,n+1,n+2,...,m] für einige n und m mit n <= m

So erhalten wir eine permutation, die p die Liste [1,2,...,N].Wir teilen die p bis in läuft r_1,r_2,...,r_M , so dass p = r_1+r_2+...+r_M.Wir sind dann auf der Suche für eine permutation q von [1,2,...,M] , so dass r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N].

Zum Beispiel, wenn p = [1,3,4,2,5,6], wir haben N=6, M=4, r_1 = [1], r_2 = [3,4], r_3 = [2] und r_4 = [5,6].In diesem Fall benötigen wir q zu [1,3,2,4] als r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6].

Beachten Sie, dass q nicht enthalten verläuft mit einer Länge größer als einen pro-definition;wenn es wäre, dann gibt es ein i < M mit q.i + 1 = q.(i+1) und damit eine Teilliste r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) von [1,2,...,N], aber r_(q.i)+r_(q.i + 1) ist auch eine Teilliste der p dem widerspricht, dass r_(q.i) und r_(q.i + 1) sind läuft.

Nun, zu finden, eine q gegeben p, wir übernehmen die Verfügbarkeit der mapping-Daten-Struktur mit O(1) Einsätze und suchen von zahlen und Listen O(1) fügt und forward traversal.Dann werden wir Folgendes tun.

• Zuerst konstruieren wir die Liste runheads = [r_1.1,r_2.1,...,r_M.1].Dies kann getan werden, trivial durch das Durchlaufen p unter Beibehaltung der aktuellen Ausführung.In diesem Schritt werden wir auch daran denken, die maximale Anzahl angetroffen zu erhalten N am Ende und erstellen Sie eine mapping heads mit den Elementen von runheads als Schlüssel.Dieser Schritt ist klar O(n).Beachten Sie, dass es nicht relevant ist, was die Werte von heads sind, so können wir nur verwenden, führen Sie r_i als Wert für den Schlüssel r_i.1.

• Als Nächstes werden wir die Iteration von 1 zu (und einschließlich) N die Pflege Wert k mit Anfangswert 1.Für jeden Wert i wir überprüfen, um zu sehen, ob i in heads.Ist dies der Fall, werden wir hinzufügen i -> k um eine Zuordnung f und erhöhen k.Dieser Schritt ist auch klar O(n).Um in der Lage sein, um wieder aus q zu p wir können auch speichern eine zusätzliche mapping rev mit k -> i oder auch k -> runheads(i) ohne zusätzliche big-O-Kosten.

• Schließlich wenden wir mapping f zu den Elementen runheads zu erhalten q.Wieder O(n).

Um mit einem Beispiel illustrieren betrachten wir den Fall, dass p = [1,3,4,2,5,6].

• Im ersten Schritt erhalten wir runheads = [1,3,2,5], N=6 und heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }.

• Für die zweiten Schritte wir vier Fälle, für die wir etwas tun müssen: 1, 2, 3 und 5.Für diese Fälle haben wir die Werte für k das sind 1, 2, 3 und 4, beziehungsweise.Dies bedeutet, dass f werden { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }.(Und rev würde { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } oder { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }, je nachdem , was Sie gewählt haben, um zu speichern.)

• Zu erhalten q wir berechnen map(f,runheads) die [f(1),f(3),f(2),f(5)] oder, was dasselbe ist, [1,3,2,4].

Also, wenn ich nicht einen Fehler machen und wenn das Daten-Strukturen erfüllen die oben genannten Anforderungen, diese Lösung sollte sein O(n).Beachten Sie, dass in der Praxis könnte es eigentlich immer sein, ist es sinnvoll, Ihre eigenen (O(n*log(n))) Lösung.Wenn Sie eine große p aber mit nur ein paar Läufe, die Sortierung runheads und verwenden, die zum erstellen des mappings könnte effizienter sein.Ich denke, dass p müsste ziemlich groß für dieses der Fall zu sein.

Answer 2

Herausgegeben für clarificaton

1. Schritt: Ausführen des Algorithmus, aber anstatt die Herstellung nur ein Hash-Tabelle eine Hash-Tabelle (D1) durch den Kopf des Satzes indexierte erzeugen ist Mapping (beispielsweise für [3,4] Das wird 3) und eine Liste (L1) mit dem Satz selbst

[3; 4; 6; 8; 1; 2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

Schritt 2: Ich Sie die Sammlungen sehen wir jetzt sehen Sie, dass für einen gegebenen Satz wir den Index haben, in denen wir es gefunden (in L1) und dem Kopf Wert. Die richtige Karte Wert wird die minimale ganze Zahl zwischen ihnen, die nicht bereits vergeben ist. Zum Beispiel für die [3,4] wir haben, dass der Wert zwischen 1 und 3 sein muß, und ist seit dem 1. bereits genommen, Nehmen der entsprechende Wert ist 2. berücksichtigt, dass, wie D1 durch den Leiter indiziert Wert, niedrigere Werte immer zu nehmen, wenn der entsprechende Satz vorhanden ist. Im Beispiel [1,2] auf 1 abgebildet, so dass dieser Schlüssel bereits „genommen“. Also, in Pseudo-Code:

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

Zum Beispiel

• nehmen wir den ersten Wert in L1 -> [3,4] ...
• erhält den Kopf = 3
• Ab 1. wir Nachschlag D1 [1], die bereits belegt ist, so dass wir erhöhen bis 2.
• Wir suchen D1 [2], die so leer ist, dass wir vergeben D1 [2] = [3,4] und D [3]
löschen

, das bietet keine O (n), sondern so etwas wie O (n + log (n)) (n für den ersten Schritt, log (n) für die zweite)

Für das obige Beispiel, dass bekommt man:

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

Nun, wenn Sie [3, 4, 8, 6; 1; 2], das in

führen

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

, weil es absolute Ordnung im ursprünglichen Array verwendet wird, weiß ich nicht, ob das alles in Ordnung ist, oder Sie werden 6 in Index 3 sein wollen und 8 in Index 4 sein, in diesem Fall werden Sie wahrscheinlich haben L1 vorzuzubestellen basierend auf dem Kopf, die Ihre Komplexität von Log erhöhen werden (n)

Wenn Sie vorzubestellen haben musst du 0 (n + log ^ 2 (n)), das ist nicht so schlecht (vielleicht weniger unter der Annahme einer QuickSort hat O (Log n) Bestellung L1 O (log (log n))