Problem
Schreibe alle Anordnungen der Zeichen von s in lexikographischer Reihenfolge auf. Für "abc" lautet die Liste abc, acb, bac, bca, cab, cba. Gib den k-ten Eintrag zurück, gezählt ab 1. Bei 12 Zeichen (479.001.600 Anordnungen) ist es zu langsam, die ganze Liste zu erzeugen. Jeder Block von Anordnungen, die mit demselben Zeichen beginnen, hat aber (Länge − 1)! Einträge, du kannst also ein Zeichen nach dem anderen festlegen.
Implementiere lexicographic_permutation(s, k).
Eingabe
s: Verschiedene Zeichen in beliebiger Reihenfolge.
k: Die Position in der sortierten Liste, gezählt ab 1.
Ausgabe
Gib die k-te Anordnung als String zurück. Zeichen werden nach ihren Zeichencodes verglichen, Ziffern kommen also vor Großbuchstaben und diese vor Kleinbuchstaben.
Einschränkungen
1 ≤ s.length ≤ 12; alle Zeichen von s sind verschieden; 1 ≤ k ≤ s.length!
Beispiele
Eingabe:
s = "abc"
k = 4
Erwartete Ausgabe:
expected = "bca"
Eingabe:
std::string s = "abc";
long long k = 4;
Erwartete Ausgabe:
std::string expected = "bca";
Eingabe:
string s = "abc";
long k = 4;
Erwartete Ausgabe:
string expected = "bca";
Erläuterung
Die Liste lautet abc, acb, bac, bca, cab, cba, und die vierte Anordnung ist "bca".
Eingabe:
s = "312"
k = 1
Erwartete Ausgabe:
expected = "123"
Eingabe:
std::string s = "312";
long long k = 1;
Erwartete Ausgabe:
std::string expected = "123";
Eingabe:
string s = "312";
long k = 1;
Erwartete Ausgabe:
string expected = "123";
Erläuterung
Die erste Anordnung sind die Zeichen in sortierter Reihenfolge: "123".
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Sortiere zuerst die Zeichen.
Hinweis 2
Jede Wahl des ersten Zeichens deckt (Länge − 1)! Permutationen ab. Teilst du k − 1 durch diese Zahl, weißt du, welches Zeichen an erster Stelle steht.
Hinweis 3
Entferne das gewählte Zeichen, behalte den Divisionsrest und wiederhole das mit den übrigen Zeichen.
Erwartete Komplexität
Zeit O(n²), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.