Interleave array in Konstante Raum

Dieses problem ist nicht so trivial, wie die Menschen machen aus zu sein. Hausaufgaben? LOL.

Dem folgenden link hat die Lösung: http://arxiv.org/abs/0805.1598

Dieses problem ist nicht so einfach, wie es scheint, aber nach einigem nachdenken, den Algorithmus, um dies zu erreichen, ist nicht allzu schlecht. Sie werden bemerken, dass das erste und Letzte element sind bereits vorhanden, so brauchen wir nicht um Sie kümmern. Wir halten Links index-variable, die darstellt, das erste Element in die erste Hälfte des Arrays, die Bedürfnisse geändert. Danach legen wir eine rechts-index-variable auf das erste Element in der 2. Hälfte des Arrays, die Bedürfnisse geändert. Alles was wir jetzt tun, ist die swap-Eintrag in der rechten index-down one-by-one, bis es erreicht die linke index-Element. Erhöhen Sie den linken index von 2, und den rechten index von 1, und wiederholen, bis die Indizes sich überschneiden oder Links geht über den rechten index (rechts-index wird am Ende immer auf den letzten index des Arrays). Erhöhen wir den linken index von zwei in jeder Zeit, weil das Element Links + 1 hat bereits natürlich fiel in Ort.

Pseudocode

1. Gesetzten Links index 1
2. Direkt index auf die Mitte (array-Länge /2)
3. Tauschen Sie das Element an die richtige index mit der Position unmittelbar vor, bis es ersetzt das Element an der linken index
4. Erhöhen Sie den linken index von 2
5. Erhöhen Sie den rechten index von 1
6. Wiederholen Sie 3 bis 5 der linken-index größer als oder gleich dem index

Interleaving-Algorithmus in C(#)

protected void Interleave(int[] arr)  
{  
    int left = 1;  
    int right = arr.Length /2;  
    int temp;  

    while (left < right)  
    {  
        for (int i = right; i > left; i--)  
        {  
            temp = arr[i];  
            arr[i] = arr[i - 1];  
            arr[i - 1] = temp;  
        }  

        left += 2;  
        right += 1;  
    }  
}    

Dieser Algorithmus arbeitet in O(1) Speicher (mit der temp-variable, die eliminiert werden konnte mit der addition/Subtraktion-swap-Technik) ich bin nicht sehr gut in der runtime Analyse, aber ich glaube, das ist immer noch O(n), obwohl wir durchführen viele swaps. Vielleicht kann jemand weitere entdecken Sie die Laufzeit-Analyse.

Zuerst die Theorie: Ordnen Sie die Elemente in 'permutation Zyklen'. Nehmen Sie ein element und platzieren Sie es an seine neue position verschieben das element aus, das wird derzeit gibt es. Dann nehmen Sie das verschobene element und steckte es in seine neue position. Dies verdrängt noch ein anderes element, so Spülen und wiederholen. Wenn das element verdrängt gehört zu der position von dem element, dem Sie die ersten Schritte mit, die Sie abgeschlossen haben, ein Zyklus.

Eigentlich, deiner ist ein Spezialfall der Frage, die ich hier, die war: Wie kann Sie anordnen einer array in beliebiger Reihenfolge in O(N) Zeit und O(1) Speicherplatz? In meiner Frage, die Positionen neu geordnet werden beschrieben durch eine Reihe von zahlen, wobei die Zahl auf die N-te position gibt den index von element im ursprünglichen array.

Jedoch, Sie nicht über diese zusätzliche Reihe in der Sie Ihr problem, und die Zuweisung würde es dauern O(N) Speicherplatz. Glücklicherweise können wir berechnen, die den Wert jedes Elements in diesem array on-the-fly, wie dieser:

int rearrange_pos(int x) {
    if (x % 2 == 0) return x /2;
    else return (x - 1) /2 + n; //where n is half the size of the total array
}

Ich nicht duplizieren die Neuordnung Algorithmus selbst hier; es sein kann gefunden in der akzeptierten Antwort auf meine Frage.

Edit: Jason hat darauf hingewiesen, die Antwort, die ich verlinkt noch reservieren muss ein array von bools, so dass es O(N) Speicherplatz. Dies ist, weil eine permutation kann aus mehreren Zyklen. Ich habe versucht, die Notwendigkeit beseitigen, für diese Reihe, die für Ihren speziellen Fall, aber ohne Erfolg.. Es scheint nicht zu sein jede brauchbare Muster. Vielleicht kann jemand anders hier helfen können.