Dynamische Programmierung: Anzahl der Möglichkeiten, mindestens N Blase Art Swaps zu bekommen?

Question

Lassen Sie uns sagen, ich habe eine Reihe von Elementen, für die eine totale Ordnung existiert. Die Blasensortierung Abstand ist die Anzahl von Swaps, die es dauern würde, um das Array zu sortieren, wenn ich eine Blasensortierung verwendet hat. Was ist eine effiziente (wahrscheinlich dynamische Programmierung beinhaltet) Art und Weise die Anzahl der möglichen Permutationen dieses Arrays zu berechnen, die eine Blase Art Abstand von weniger als oder gleich eine vorher festgelegten Anzahl hat?

Wenn es das Problem vereinfacht, können Sie davon ausgehen, dass alle Elemente des Arrays eindeutig sind (keine Bindungen).

Answer 1

Ok, hier ist eine Lösung. Nehmen wir an, dass alle Elemente des Arrays verschieden sind, und weiter, ohne Beschränkung der Allgemeinheit können wir annehmen, dass sie {1, ..., n}. (Wir können immer die Elemente neu kennzeichnen, so dass dies der Fall ist, und nichts wird beeinträchtigt.)

Erstens können wir beobachten, dass die Anzahl der durch Blasensortierung durchgeführt Swaps ist die Anzahl von Inversionen in der Permutation a [1..n]: die Anzahl der Paare (i, j) solche dass i a [j]. (Dies ist nicht allzu schwer zu beweisen.)

So wollen wir die Anzahl der Permutationen von {1, ..., n} mit höchstens k Inversionen. Sei c (n, k) bezeichnen diese Zahl. Jede Permutation von {1, ... n} kann man sich als Einnahme eine Permutation von {1, ..., n-1} und Einfügen {n} in sie irgendwo. Wenn Sie es an der Position i einfügen, erstellt es genau n-i neue Inversionen. So ist die alte Permutation muss höchstens k- (n-i) Inversionen gehabt haben. Dies ergibt:

c(n,k) = sum_{i s.t. n-i≤k} c(n-1, k-(n-i))
       = sum_{i=max(1,n-k) to n} c(n-1, k-n+i)

Und der Basisfall:

c(1,0) = 1 (or better, c(0,0)=1)

(Man beachte, daß k ist höchstens n * (n-1) / 2 2 .)

---

Update : Die oben nimmt O (n ^ 2k) - so bis zu O (n ^ 4) - time c zu berechnen (n, k), da jeder der nk c (n, k) 's dauert O (n) Zeit die früheren gegeben zu berechnen. Wir können, indem sie das erneute Auftreten kürzer, um einen Faktor von n verbessern, so dass jeder c (n, k) kann in O (1) Zeit gegeben frühere berechnet werden. Schreiben Sie j für k-n + i, so dass

c(n,k) = sum_{j=max(k-n+1,0) to k} c(n-1, j)

Beachten Sie, dass der größte Teil der Summe für c ist die gleiche (n, k) und C (n, k-1). Insbesondere

When k≤n-1, c(n,k) = c(n,k-1) + c(n-1,k)
When k≥n,   c(n,k) = c(n,k-1) + c(n-1,k) - c(n-1,k-n)

---

Aktualisiert Programm: (. Ich schrieb eine faule memoised Version, man kann es es von unten nach oben, indem sie die üblichen Art und Weise mit dynamischer Programmierung etwas effizienter machen kann)

ct = {(0,0): 1}
def c(n,k):
    if k<0: return 0
    k = min(k, n*(n-1)/2) #Or we could directly return n! if k>=n*(n-1)/2
    if (n,k) in ct: return ct[(n,k)]
    ct[(n,k)] = c(n,k-1) + c(n-1,k) - c(n-1,k-n)
    return ct[(n,k)]

if __name__ == "__main__":
    n = input("Size of array: ")
    k = input("Bubble-sort distance at most: ")
    print c(n,k)

Answer 2

Haben Sie einen Blick auf die Wagner-Fisher-Algorithmus bearbeiten Distanzen. Du bist wahrscheinlich die gleiche Richtung. Eine Tabelle von mindestens Swaps konstruieren, die n × sollte n in Ihrem Problem, eine unveränderliche Beziehung mit thatlets Sie die Tabelle von oben links nach unten rechts bauen