024 – Millionenste lexikografische Permutation

 

Unter einer Permutation versteht man die Veränderung der Anordnung einer Menge durch Vertauschen ihrer Elemente. Zum Beispiel ist 3124 eine mögliche Permutation der Ziffern 1, 2, 3, 4. Wenn alle Permutationen nach ihrem Betrag sortiert sind, stehen sie in lexikografischer Ordnung. Die lexikografischen Permutationen von 0, 1 und 2 sind:

012 021 102 120 201 210

Was ist die millionenste lexikografische Permutation der Ziffern 0, 1, 2, 3, 4, 5, 6, 7, 8 und 9?

Lösung

Wir können die gesuchte Permutation Ziffernweise erstellen und müssen nicht alle 1000000 vorhergehenden Permutationen durchlaufen.

Die Anzahl der Möglichkeiten, n Elemente anzuordnen, ist n! (Fakultät). Wie wir dies nutzen zeigen wir an einem kleineren Beispiel: Die 10te Permutation von 0, 1, 2 und 3.

Wir haben 4 Ziffern. Um die erste Ziffer der gesuchten Permutation zu bestimmen, nutzen wir, dass es 3! = 6 Möglichkeiten gibt, die restlichen drei Ziffern anzuordnen. Das bedeutet, dass bei den ersten 6 lexikografischen Permutationen die 0 vorne steht. Bei der 7ten bis 12ten steht die 1 vorne. Wir können daher sicher sein, dass die erste Ziffer der 10ten Permutation die 1 ist.

Wir löschen die 1 aus dem Feld, es bleibt: [0 2 3].
Es gibt noch drei Ziffern. Um die letzten zwei anzuordnen gibt es 2! = 2 Möglichkeiten. Bei der 7ten und 8ten Permutation steht also die 0 vorne, bei der 9ten und 10ten die 2. Wir kennen damit von der gesuchten Permutation schon [1 2 _ _]. Es bleibt übrig: [0 3]

Es gibt nun noch zwei Ziffern. Um die letzte Ziffer anzuordnen gibt es eine Möglichkeit. Bei der 9ten Permutation steht also die 0 vorne, bei der 10ten die 3. Wir wissen nun, dass die gesuchte Permutation mit [1 2 3 _] beginnt. Es bleibt nur noch die 0 übrig, diese muss daher an letzter Stelle stehen: [1 2 3 0].

Dieses Verfahren übernehmen wir für die größere Aufgabe. Ist die Nummer n der gesuchten Permutation eine gerade Zahl, kann es zu Problemen kommen, daher suchen wir die Permutation der nächstkleineren ungeraden Zahl n-1.

Matlab-Code:

clear
tic

gesucht = 1e6;
ziffern = 0 : 9;
ergebnis = [];

if (mod(gesucht, 2) == 0)
    gesucht = gesucht - 1;
    flip = 1;
else
    flip = 0;
end

while gesucht > 0
    i = length(ziffern) - 1;
    j = floor(gesucht / factorial(i));
    gesucht = gesucht - j * factorial(i);

    if (gesucht > 0)
        j = j + 1;       % da die erste Ziffer 0 ist
        ergebnis = [ergebnis ziffern(j)];

        % benutzte Ziffer entfernen:
        ziffern = [ziffern(1 : j - 1) ziffern(j + 1 : end)];
    end
end

ergebnis = [ergebnis ziffern];
if (flip == 1)
    ergebnis(end - 1 : end) = fliplr(ergebnis(end - 1 : end));
end

disp(ergebnis)
toc

Ergebnis: 2 7 8 3 9 1 5 4 6 0
Rechenzeit: 0.000690 Sekunden

Ähnliche Artikel

Kommentar verfassen