The problem asks for the millionth permutation of the digits \(0,1,2,\dots,9\) when all \(10!\) permutations are listed in lexicographic order. More generally, given any ordered set of \(n\) distinct symbols and a 1-based index \(k\), we want the \(k\)-th lexicographic permutation.
Generating every permutation up to the target would be wasteful, because \(10!=3{,}628{,}800\). The key fact is that lexicographic order is organized into factorial-sized blocks, so the desired permutation can be addressed directly from its rank.
Let the available symbols be \(A=\{a_0<a_1<\cdots<a_{n-1}\}\), and let \(r=k-1\) be the 0-based rank. The entire method is a repeated answer to one question: which block of size \((m-1)!\) contains the target permutation when \(m\) symbols remain?
Fix the first symbol of a permutation of \(m\) distinct symbols. The remaining \(m-1\) symbols can then be arranged in exactly \((m-1)!\) ways. Therefore the lexicographic list splits into consecutive blocks of size \((m-1)!\), one block for each possible first symbol in sorted order.
If the current 0-based rank is \(r\), then the correct block number is
$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$
so the next symbol is the \(q\)-th smallest unused symbol. After choosing it, the rank inside that block becomes
$$r'=r\bmod (m-1)!.$$
This gives a clean recurrence. If \(T(A,r)\) denotes the permutation of rank \(r\) among the symbols in \(A\), and if \(A=\{a_0<\cdots<a_{m-1}\}\), then with \(q=\lfloor r/(m-1)!\rfloor\) and \(r'=r\bmod (m-1)!\),
$$T(A,r)=a_q\text{ followed by }T(A\setminus\{a_q\},r').$$
The base case is \(T(\{a\},0)=a\). The invariant is simple and crucial: after fixing a prefix, the updated rank is always the lexicographic rank of the remaining suffix among the remaining unused symbols.
The same procedure can be written as a factorial-number-system expansion:
$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$
with \(0\le c_i\le i\). These coefficients are unique. At step \(i\), the coefficient \(c_i\) tells us which remaining symbol to take from the sorted pool. In permutation language, \((c_{n-1},c_{n-2},\dots,c_0)\) is the Lehmer code of the answer.
This viewpoint explains why no backtracking is needed: each quotient fixes one position permanently, and each remainder passes the unresolved part of the problem to the next smaller factorial scale.
For the original problem we convert from 1-based to 0-based rank:
$$r=1{,}000{,}000-1=999{,}999.$$
Its factoradic expansion is
$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$$
So we choose, in order, the \(2\)-nd, \(6\)-th, \(6\)-th, \(2\)-nd, \(5\)-th, \(1\)-st, \(2\)-nd, \(1\)-st, \(1\)-st, and \(0\)-th remaining digits. Starting from \([0,1,2,3,4,5,6,7,8,9]\), those choices produce
$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$$
hence the millionth lexicographic permutation is
$$2783915460.$$
The C++, Python, and Java implementations accept a symbol string and a 1-based permutation index, then sort the symbols so that lexicographic order is defined unambiguously. They compute \(n!\) for the symbol count and reject any request outside the valid range \(1\le k\le n!\).
After that, the implementation converts \(k\) to the 0-based rank \(r=k-1\), stores the remaining symbols in a mutable ordered pool, and repeats the quotient-remainder step. At each round it divides by \((m-1)!\), uses the quotient as an index into the pool, appends the chosen symbol to the answer, removes it from the pool, and continues with the remainder.
The implementations also include small checkpoints such as the first and last permutations of the symbols \(0,1,2\), which verify that the ordering and the off-by-one convention are correct before solving the main case.
There are \(n\) selection rounds. In these implementations the remaining symbols are kept in a simple list or array-like structure, so removing the chosen symbol costs \(O(n)\) in the worst case. The total running time is therefore \(O(n^2)\), and the extra space is \(O(n)\).
For the original input \(n=10\), this cost is tiny. The important gain is conceptual: the algorithm computes one target permutation directly instead of enumerating all \(10!\) permutations that come before it.
Gesucht ist die millionste Permutation der Ziffern \(0,1,2,\dots,9\), wenn alle \(10!\) Permutationen lexikographisch sortiert werden. Allgemeiner: Zu einer geordneten Menge von \(n\) verschiedenen Symbolen und einem 1-indizierten Rang \(k\) soll die \(k\)-te lexikographische Permutation bestimmt werden.
Alle Permutationen bis zum Ziel explizit zu erzeugen wäre unnötig, denn schon \(10!=3{,}628{,}800\). Die Struktur der lexikographischen Ordnung ist jedoch stark genug, um direkt vom Rang zur gesuchten Permutation zu springen.
Seien die verfügbaren Symbole \(A=\{a_0<a_1<\cdots<a_{n-1}\}\), und setze \(r=k-1\) als 0-indizierten Rang. Die ganze Methode beruht darauf, die Permutationsliste immer wieder in Blöcke der Größe \((m-1)!\) zu zerlegen, wenn noch \(m\) Symbole übrig sind.
Fixiert man bei \(m\) verschiedenen Symbolen das erste Symbol, dann können die verbleibenden \(m-1\) Symbole in genau \((m-1)!\) Weisen angeordnet werden. Deshalb zerfällt die lexikographische Liste in aufeinanderfolgende Blöcke der Länge \((m-1)!\), einen Block pro möglichem ersten Symbol in sortierter Reihenfolge.
Für den aktuellen 0-basierten Rang \(r\) ist die richtige Blocknummer
$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$
also ist das nächste Symbol das \(q\)-te kleinste noch nicht benutzte Symbol. Innerhalb dieses Blocks bleibt dann der Rest-Rang
$$r'=r\bmod (m-1)!.$$
Damit erhält man eine echte Rekursion. Bezeichne \(T(A,r)\) als die Permutation vom Rang \(r\) auf der sortierten Symbolmenge \(A=\{a_0<\cdots<a_{m-1}\}\). Mit \(q=\lfloor r/(m-1)!\rfloor\) und \(r'=r\bmod (m-1)!\) gilt
$$T(A,r)=a_q\text{ gefolgt von }T(A\setminus\{a_q\},r').$$
Der Anfangsfall ist \(T(\{a\},0)=a\). Die entscheidende Invariante lautet: Nach jedem fest gewählten Präfix ist der aktualisierte Rang genau der lexikographische Rang des verbleibenden Suffixes unter den noch nicht verwendeten Symbolen.
Dasselbe Verfahren kann als Darstellung im Fakultätenzahlensystem geschrieben werden:
$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$
wobei \(0\le c_i\le i\). Diese Koeffizienten sind eindeutig. In jedem Schritt sagt \(c_i\), welches Element aus der aktuell sortierten Restmenge ausgewählt werden muss. In der Sprache der Permutationen ist \((c_{n-1},c_{n-2},\dots,c_0)\) der Lehmer-Code der gesuchten Permutation.
Gerade diese Eindeutigkeit macht die Methode so effizient: Jeder Quotient fixiert eine Position endgültig, und jeder Rest übergibt nur den noch ungelösten Teil an die nächste kleinere Fakultätsstufe.
Für die Originalaufgabe wird zuerst auf 0-basierte Zählung umgestellt:
$$r=1{,}000{,}000-1=999{,}999.$$
Die faktoradische Entwicklung lautet
$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$$
Also wählt man der Reihe nach die \(2\)-te, \(6\)-te, \(6\)-te, \(2\)-te, \(5\)-te, \(1\)-te, \(2\)-te, \(1\)-te, \(1\)-te und \(0\)-te verbleibende Ziffer. Ausgehend von \([0,1,2,3,4,5,6,7,8,9]\) entsteht so
$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$$
und damit ist die millionste lexikographische Permutation
$$2783915460.$$
Die Implementierungen in C++, Python und Java akzeptieren eine Symbolfolge und einen 1-indizierten Permutationsrang, sortieren die Symbole und berechnen \(n!\). Liegt der gewünschte Rang nicht im Bereich \(1\le k\le n!\), wird der Aufruf verworfen.
Danach wird \(k\) in den 0-basierten Rang \(r=k-1\) umgerechnet. Die noch verfügbaren Symbole liegen in einem veränderbaren, sortierten Vorrat. In jeder Runde wird durch \((m-1)!\) dividiert, der Quotient als Index benutzt, das entsprechende Symbol an die Ausgabe angehängt, aus dem Vorrat entfernt und mit dem Rest weitergerechnet.
Zusätzlich enthalten die Implementierungen kleine Prüffälle, etwa die erste und die letzte Permutation der Symbole \(0,1,2\). Damit wird abgesichert, dass sowohl die Reihenfolge als auch die Off-by-one-Behandlung korrekt sind.
Es gibt \(n\) Auswahlrunden. Da die Restmenge in diesen Implementierungen als einfache Liste beziehungsweise feldähnliche Struktur gespeichert wird, kostet das Entfernen des gewählten Elements im schlechtesten Fall \(O(n)\). Insgesamt ergibt sich daher eine Laufzeit von \(O(n^2)\) und ein zusätzlicher Speicherbedarf von \(O(n)\).
Für den Originalfall \(n=10\) ist das vernachlässigbar klein. Der eigentliche Gewinn liegt darin, dass die gesuchte Permutation direkt konstruiert wird, statt alle \(10!\) vorherigen Permutationen zu erzeugen.
Problem, \(0,1,2,\dots,9\) rakamlarının bütün \(10!\) permütasyonları leksikografik sırada yazıldığında milyonuncu permütasyonu bulmayı ister. Daha genel biçimde, sıralı \(n\) farklı sembol ve 1-indeksli bir \(k\) değeri verildiğinde, \(k\)-ıncı leksikografik permütasyon aranır.
Hedefe kadar bütün permütasyonları üretmek gereksizdir; çünkü \(10!=3{,}628{,}800\). Asıl fikir, leksikografik sıranın faktöriyel boyutlu bloklara ayrılması sayesinde istenen permütasyona doğrudan rütbesinden gitmektir.
Elde kalan semboller \(A=\{a_0<a_1<\cdots<a_{n-1}\}\) olsun ve 1-indeksli sıra yerine \(r=k-1\) ile 0-indeksli rütbeyi kullanalım. Yöntem tamamen şu gözleme dayanır: \(m\) sembol kaldığında, aynı ilk sembolle başlayan permütasyonların sayısı tam olarak \((m-1)!\) olur.
\(m\) farklı sembolden oluşan bir permütasyonda ilk sembol sabitlenirse, geriye kalan \(m-1\) sembol \((m-1)!\) farklı şekilde sıralanabilir. Bu yüzden leksikografik liste, her biri \((m-1)!\) uzunluğunda ardışık bloklara ayrılır ve her blok sıralı listedeki bir ilk sembole karşılık gelir.
Geçerli 0-tabanlı rütbe \(r\) için doğru blok numarası
$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor$$
olur; yani sıradaki sembol, henüz kullanılmamış semboller içindeki \(q\)-ıncı en küçük semboldür. Bu seçimden sonra blok içindeki yeni rütbe
$$r'=r\bmod (m-1)!$$
şeklindedir.
\(T(A,r)\), \(A\) kümesindeki semboller üzerinde rütbesi \(r\) olan permütasyon olsun. Eğer \(A=\{a_0<\cdots<a_{m-1}\}\) ise, \(q=\lfloor r/(m-1)!\rfloor\) ve \(r'=r\bmod (m-1)!\) için
$$T(A,r)=a_q\text{ ardından }T(A\setminus\{a_q\},r')$$
yazılır. Başlangıç durumu \(T(\{a\},0)=a\) olur. Buradaki temel invariant şudur: Her önek sabitlendiğinde yeni rütbe, kalan semboller üzerinde aranan son ekin tam leksikografik rütbesi olarak kalır.
Aynı süreç, rütbenin faktöriyel sayı sistemi açılımı olarak da görülebilir:
$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$
burada \(0\le c_i\le i\). Bu katsayılar tektir. Her adımda \(c_i\), sıralı kalan havuzdan hangi sembolün seçileceğini söyler. Permütasyon kuramında \((c_{n-1},c_{n-2},\dots,c_0)\) dizisi, sonucun Lehmer kodudur.
Dolayısıyla arama, geri izleme gerektiren bir süreç değildir; her bölüm bir konumu kesinleştirir, her kalan ise problemi bir alt faktöriyel ölçeğe indirir.
Orijinal problemde önce 1-indeksli sayı 0-indeksliye çevrilir:
$$r=1{,}000{,}000-1=999{,}999.$$
Bunun faktöriyel sayı sistemi açılımı
$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!$$
şeklindedir. Yani sırayla kalan rakamlar içinden \(2\)-nci, \(6\)-ncı, \(6\)-ncı, \(2\)-nci, \(5\)-inci, \(1\)-inci, \(2\)-nci, \(1\)-inci, \(1\)-inci ve \(0\)-ıncı seçim yapılır. Başlangıç havuzu \([0,1,2,3,4,5,6,7,8,9]\) olduğunda elde edilen sıra
$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0$$
olur; dolayısıyla milyonuncu leksikografik permütasyon
$$2783915460$$
çıkar.
C++, Python ve Java uygulamaları bir sembol dizisi ile 1-indeksli permütasyon sırasını alır, sembolleri sıralar ve \(n!\) değerini hesaplar. İstenen sıra \(1\le k\le n!\) aralığının dışındaysa işlem hata olarak durdurulur.
Daha sonra \(k\) değeri \(r=k-1\) ile 0-tabanlı rütbeye çevrilir. Kalan semboller sıralı ve değiştirilebilir bir havuzda tutulur. Her adımda \((m-1)!\) ile bölüm ve kalan alınır; bölüm havuz içindeki indekstir, seçilen sembol cevaba eklenir, havuzdan silinir ve işlem kalan ile devam eder.
Uygulamalar ayrıca \(0,1,2\) sembolleri üzerindeki ilk ve son permütasyon gibi küçük kontrol örnekleri de içerir. Böylece hem sıralama mantığı hem de bir eksik-bir fazla hatası kontrol edilmiş olur.
Toplam \(n\) seçim turu vardır. Bu uygulamalarda kalan semboller basit bir liste ya da dizi-benzeri yapı içinde tutulduğu için, seçilen elemanı aradan çıkarmak en kötü durumda \(O(n)\) sürer. Bu nedenle toplam zaman karmaşıklığı \(O(n^2)\), ek bellek kullanımı ise \(O(n)\) olur.
Orijinal girdi için \(n=10\) olduğundan bu maliyet çok küçüktür. Asıl kazanç, çözümün hedef permütasyonu doğrudan üretmesidir; ondan önce gelen bütün \(10!\) permütasyonları saymaya gerek kalmaz.
La tarea pide la permutación número un millón de los dígitos \(0,1,2,\dots,9\) cuando las \(10!\) permutaciones se ordenan lexicográficamente. En forma más general, dados \(n\) símbolos distintos y ordenados, y un índice 1-basado \(k\), queremos la \(k\)-ésima permutación lexicográfica.
Generar todas las permutaciones anteriores al objetivo sería innecesario, porque \(10!=3{,}628{,}800\). La estructura combinatoria de ese orden permite saltar directamente al resultado usando el rango de la permutación.
Sea \(A=\{a_0<a_1<\cdots<a_{n-1}\}\) el conjunto de símbolos disponibles, y sea \(r=k-1\) el rango en base 0. El punto clave es que, cuando quedan \(m\) símbolos, las permutaciones se agrupan en bloques consecutivos de tamaño \((m-1)!\).
Si fijamos el primer símbolo de una permutación de \(m\) símbolos distintos, los \(m-1\) restantes se pueden ordenar de exactamente \((m-1)!\) maneras. Por eso la lista lexicográfica se parte en bloques consecutivos de longitud \((m-1)!\), uno por cada posible primer símbolo en el orden natural.
Para un rango actual \(r\), el número de bloque correcto es
$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$
de modo que el siguiente símbolo es el \(q\)-ésimo símbolo no usado dentro de la lista ordenada. Después de esa elección, el nuevo rango interno es
$$r'=r\bmod (m-1)!.$$
Si \(T(A,r)\) representa la permutación de rango \(r\) sobre \(A=\{a_0<\cdots<a_{m-1}\}\), entonces con \(q=\lfloor r/(m-1)!\rfloor\) y \(r'=r\bmod (m-1)!\) se cumple
$$T(A,r)=a_q\text{ seguido de }T(A\setminus\{a_q\},r').$$
El caso base es \(T(\{a\},0)=a\). La invariante importante es que, una vez fijado un prefijo, el valor actualizado de \(r\) sigue siendo exactamente el rango lexicográfico del sufijo buscado entre los símbolos que aún no se han usado.
El mismo procedimiento se puede escribir como una expansión en el sistema factorial:
$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$
con \(0\le c_i\le i\). Esos coeficientes son únicos. En cada paso, \(c_i\) indica qué posición debe elegirse dentro del conjunto ordenado de símbolos restantes. En términos de permutaciones, \((c_{n-1},c_{n-2},\dots,c_0)\) es el código de Lehmer de la respuesta.
Eso explica por qué el algoritmo no necesita prueba y error: cada cociente fija una posición de manera definitiva y cada resto transmite solo la parte aún no resuelta a la siguiente escala factorial.
En el caso original primero convertimos el índice 1-basado a rango 0-basado:
$$r=1{,}000{,}000-1=999{,}999.$$
Su expansión factorial es
$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$$
Por lo tanto hay que escoger, sucesivamente, el \(2\)-do, \(6\)-to, \(6\)-to, \(2\)-do, \(5\)-to, \(1\)-ro, \(2\)-do, \(1\)-ro, \(1\)-ro y \(0\)-mo dígito restante. Empezando desde \([0,1,2,3,4,5,6,7,8,9]\), esas elecciones producen
$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$$
y por tanto la millonésima permutación lexicográfica es
$$2783915460.$$
Las implementaciones en C++, Python y Java reciben una cadena de símbolos y un índice de permutación 1-basado, ordenan los símbolos y calculan \(n!\). Si el índice solicitado queda fuera del intervalo \(1\le k\le n!\), el cálculo se rechaza.
Luego convierten \(k\) en el rango 0-basado \(r=k-1\). Los símbolos restantes se guardan en un contenedor ordenado y mutable. En cada iteración se divide por \((m-1)!\), el cociente se usa como índice del siguiente símbolo, ese símbolo se añade a la respuesta, se elimina del contenedor y se continúa con el resto.
Además, las implementaciones incluyen comprobaciones pequeñas, como la primera y la última permutación de los símbolos \(0,1,2\). Esas pruebas detectan enseguida errores de orden o de desajuste entre índice 1-basado y 0-basado.
Hay \(n\) rondas de selección. En estas implementaciones, los símbolos restantes se mantienen en una lista o estructura tipo arreglo, así que borrar el elemento elegido cuesta \(O(n)\) en el peor caso. El tiempo total es entonces \(O(n^2)\) y el espacio extra es \(O(n)\).
Para el caso original con \(n=10\), ese costo es mínimo. La mejora esencial es que el algoritmo obtiene directamente la única permutación deseada, en vez de enumerar las \(10!\) permutaciones posibles.
题目要求把数字 \(0,1,2,\dots,9\) 的全部 \(10!\) 个排列按字典序排好，然后取其中第 \(1{,}000{,}000\) 个。更一般地说，给定一个已经排好顺序的 \(n\) 个不同符号，以及一个从 1 开始计数的下标 \(k\)，要直接求出第 \(k\) 个字典序排列。
如果从头枚举到目标位置，代价很不必要，因为 \(10!=3{,}628{,}800\)。这道题真正利用的是字典序排列天然会分成若干个大小为阶乘的块，因此可以从排名直接定位到答案。
设当前可用符号集合为 \(A=\{a_0<a_1<\cdots<a_{n-1}\}\)，并把题目给出的 1 基下标改写成 0 基排名 \(r=k-1\)。整个方法反复回答同一个问题：当还剩 \(m\) 个符号时，目标排列落在长度为 \((m-1)!\) 的哪一个字典序块里？
对 \(m\) 个不同符号的排列来说，一旦首位被固定，剩下的 \(m-1\) 个符号就正好有 \((m-1)!\) 种排法。因此字典序列表会被切成连续的块，每个块长度都是 \((m-1)!\)，而且这些块依次对应首位取排序后第 \(0\) 个、第 \(1\) 个、一直到第 \(m-1\) 个符号。
于是对于当前的 0 基排名 \(r\)，正确的块编号就是
$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$
也就是说，下一位应当选择“剩余有序符号池”中的第 \(q\) 个元素。选完以后，块内部的新排名变成
$$r'=r\bmod (m-1)!.$$
记 \(T(A,r)\) 为集合 \(A\) 上排名为 \(r\) 的排列。若 \(A=\{a_0<\cdots<a_{m-1}\}\)，并定义 \(q=\lfloor r/(m-1)!\rfloor\)、\(r'=r\bmod (m-1)!\)，则有递推规则
$$T(A,r)=a_q\text{ 后接 }T(A\setminus\{a_q\},r').$$
边界情况是 \(T(\{a\},0)=a\)。这里最重要的不变量是：每当我们固定一个前缀以后，更新后的 \(r'\) 仍然恰好表示“在剩余符号形成的所有后缀中，目标后缀的字典序排名”。
同一个过程也可以写成阶乘进位制展开：
$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$
其中 \(0\le c_i\le i\)。这些系数是唯一的。第 \(i\) 层系数 \(c_i\) 的含义非常直接：它告诉我们，在当前剩余且已经排好序的符号中，应当拿走第几个。
从排列论的角度看，\((c_{n-1},c_{n-2},\dots,c_0)\) 就是目标排列的 Lehmer 码。正因为展开唯一，所以每一步的商都会永久确定一位，而余数只把尚未解决的部分传给更小的阶乘尺度。
先把题目的 1 基编号改成 0 基排名：
$$r=1{,}000{,}000-1=999{,}999.$$
它的阶乘进位制展开为
$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$$
这意味着要依次从剩余数字中取第 \(2\)、第 \(6\)、第 \(6\)、第 \(2\)、第 \(5\)、第 \(1\)、第 \(2\)、第 \(1\)、第 \(1\)、第 \(0\) 个。起始池为 \([0,1,2,3,4,5,6,7,8,9]\)，于是依次得到
$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$$
所以题目的答案就是
$$2783915460.$$
C++、Python 和 Java 三个实现都接收一个符号串和一个从 1 开始的排列编号，然后先对符号排序，使字典序定义明确。接着它们计算当前符号个数对应的 \(n!\)，并检查请求是否满足 \(1\le k\le n!\)。
之后，程序把 \(k\) 改写为 0 基排名 \(r=k-1\)，把剩余符号存放在一个可删除元素的有序容器中，并重复执行“整除加取余”这一步：用 \((m-1)!\) 去除当前 \(r\)，商决定该选哪一个剩余符号，余数则成为下一轮在更小问题中的排名。
实现里还包含一些很小的校验样例，例如符号 \(0,1,2\) 的第一个和最后一个排列。这些检查可以快速确认字典序方向以及 1 基与 0 基转换都没有出错。
总共有 \(n\) 轮选择。在这些实现里，剩余符号保存在简单的列表或数组式结构里，因此删除中间某个元素在最坏情况下需要 \(O(n)\) 时间。总时间复杂度于是是 \(O(n^2)\)，额外空间复杂度是 \(O(n)\)。
对原题的 \(n=10\) 来说，这个代价极小。真正重要的是，算法直接构造唯一目标排列，而不是先生成全部 \(10!\) 个排列再去取第 \(1{,}000{,}000\) 个。
В задаче требуется найти миллионную перестановку цифр \(0,1,2,\dots,9\), если все \(10!\) перестановок расположить в лексикографическом порядке. В более общем виде: для упорядоченного набора из \(n\) различных символов и 1-индексированного номера \(k\) нужно получить \(k\)-ю лексикографическую перестановку.
Перебирать все перестановки до нужной позиции неразумно, потому что уже \(10!=3{,}628{,}800\). Важнее понять, как устроен сам лексикографический порядок: он разбивается на блоки факториального размера, и это позволяет перейти от номера сразу к ответу.
Пусть доступные символы образуют упорядоченное множество \(A=\{a_0<a_1<\cdots<a_{n-1}\}\), а \(r=k-1\) есть ранг в нумерации с нуля. Вся схема основана на одном наблюдении: когда осталось \(m\) символов, все перестановки с фиксированным первым символом образуют ровно \((m-1)!\) вариантов.
Если у перестановки из \(m\) различных символов зафиксировать первый символ, то остальные \(m-1\) символов можно упорядочить ровно \((m-1)!\) способами. Поэтому весь лексикографический список распадается на последовательные блоки длины \((m-1)!\), по одному блоку на каждый возможный первый символ в сортированном порядке.
Для текущего 0-индексированного ранга \(r\) номер нужного блока равен
$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$
то есть следующим символом должен стать \(q\)-й по счету среди еще не использованных символов. После этого новый внутренний ранг внутри выбранного блока равен
$$r'=r\bmod (m-1)!.$$
Обозначим через \(T(A,r)\) перестановку ранга \(r\) на множестве \(A=\{a_0<\cdots<a_{m-1}\}\). Тогда при \(q=\lfloor r/(m-1)!\rfloor\) и \(r'=r\bmod (m-1)!\) получаем
$$T(A,r)=a_q\text{, а затем }T(A\setminus\{a_q\},r').$$
Базовый случай имеет вид \(T(\{a\},0)=a\). Ключевой инвариант здесь таков: после фиксации каждого префикса обновленный ранг по-прежнему является точным лексикографическим рангом искомого суффикса среди оставшихся неиспользованных символов.
Тот же самый процесс можно записать как разложение в факториальной системе:
$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$
где \(0\le c_i\le i\). Эти коэффициенты единственны. На каждом шаге коэффициент \(c_i\) сообщает, какой по счету элемент нужно взять из текущего отсортированного набора оставшихся символов.
В терминах теории перестановок набор \((c_{n-1},c_{n-2},\dots,c_0)\) является кодом Лемера искомой перестановки. Именно поэтому алгоритму не нужен перебор: каждый частный фиксирует одну позицию окончательно, а остаток переносит задачу на следующую, меньшую факториальную шкалу.
В исходной задаче сначала надо перейти от 1-индексации к 0-индексации:
$$r=1{,}000{,}000-1=999{,}999.$$
Его разложение в факториальной системе таково:
$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$$
Значит, нужно последовательно брать \(2\)-й, \(6\)-й, \(6\)-й, \(2\)-й, \(5\)-й, \(1\)-й, \(2\)-й, \(1\)-й, \(1\)-й и \(0\)-й элемент среди оставшихся цифр. Начиная с набора \([0,1,2,3,4,5,6,7,8,9]\), получаем
$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$$
поэтому миллионная лексикографическая перестановка равна
$$2783915460.$$
Реализации на C++, Python и Java принимают строку символов и 1-индексированный номер перестановки, затем сортируют символы и вычисляют \(n!\). Если запрошенный номер не лежит в диапазоне \(1\le k\le n!\), вычисление останавливается с ошибкой.
После этого \(k\) переводится в 0-индексированный ранг \(r=k-1\). Оставшиеся символы хранятся в изменяемом упорядоченном контейнере. На каждой итерации программа делит текущий ранг на \((m-1)!\), использует частное как индекс следующего символа, добавляет выбранный символ к ответу, удаляет его из контейнера и продолжает с остатком.
В коде есть и небольшие контрольные примеры, например первая и последняя перестановки для символов \(0,1,2\). Такие проверки быстро подтверждают, что и порядок, и переход от 1-индексации к 0-индексации реализованы правильно.
Всего выполняется \(n\) шагов выбора. В этих реализациях оставшиеся символы находятся в простой списковой или массивной структуре, поэтому удаление выбранного элемента в худшем случае стоит \(O(n)\). Отсюда полное время работы равно \(O(n^2)\), а дополнительная память равна \(O(n)\).
Для исходного случая \(n=10\) это очень мало. Содержательная выгода в другом: алгоритм сразу строит нужную перестановку, а не перебирает все \(10!\) вариантов до нее.
تطلب المسألة إيجاد التبديل رقم مليون للأرقام \(0,1,2,\dots,9\) عندما تُرتَّب جميع التبديلات وعددها \(10!\) ترتيبًا معجميًا. وبصياغة أعم، إذا أُعطيَت مجموعة مرتبة من \(n\) رموز مختلفة مع رتبة 1-مفهرسة \(k\)، فنريد استخراج التبديل المعجمي رقم \(k\) مباشرة.
توليد جميع التبديلات السابقة للوصول إلى الهدف غير ضروري، لأن \(10!=3{,}628{,}800\). الفكرة الأساسية هي أن الترتيب المعجمي ينقسم طبيعيًا إلى كتل أحجامها عوامل، وبذلك يمكن الانتقال من الرتبة إلى الجواب دون تعداد شامل.
لنفرض أن الرموز المتاحة هي \(A=\{a_0<a_1<\cdots<a_{n-1}\}\)، ولنحوّل الرتبة من العد 1-المفهرس إلى رتبة 0-مفهرسة \(r=k-1\). كل الطريقة تعتمد على سؤال واحد يتكرر في كل مرحلة: عندما يبقى \(m\) رمزًا، في أي كتلة من الكتل ذات الحجم \((m-1)!\) يقع التبديل المطلوب؟
إذا ثبتنا الرمز الأول في تبديل مكوَّن من \(m\) رموز مختلفة، فإن الرموز \(m-1\) الباقية يمكن ترتيبها بعدد دقيق هو \((m-1)!\). لذلك تنقسم القائمة المعجمية إلى كتل متتالية طول كل منها \((m-1)!\)، وتمثل هذه الكتل جميع الاختيارات الممكنة للرمز الأول وفق الترتيب التصاعدي.
وبالتالي، إذا كانت الرتبة الحالية هي \(r\)، فإن رقم الكتلة المناسبة هو
$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$
أي إن الرمز التالي هو الرمز غير المستخدم رقم \(q\) داخل القائمة المرتبة. وبعد اختياره تصبح الرتبة الجديدة داخل الكتلة
$$r'=r\bmod (m-1)!.$$
إذا رمزنا بـ \(T(A,r)\) إلى التبديل ذي الرتبة \(r\) على المجموعة \(A=\{a_0<\cdots<a_{m-1}\}\)، فإننا مع \(q=\lfloor r/(m-1)!\rfloor\) و\(r'=r\bmod (m-1)!\) نحصل على
$$T(A,r)=a_q\text{ ثم }T(A\setminus\{a_q\},r').$$
أما حالة الأساس فهي \(T(\{a\},0)=a\). والثابت المهم هنا هو أن الرتبة المحدَّثة بعد تثبيت أي بادئة تبقى تمامًا رتبة اللاحقة المطلوبة بين جميع ترتيبات الرموز التي لم تُستخدم بعد.
يمكن كتابة العملية نفسها على صورة توسع في نظام العد العاملي:
$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$
حيث \(0\le c_i\le i\). هذه المعاملات وحيدة تمامًا. وفي كل مرحلة يحدد المعامل \(c_i\) أي عنصر يجب أخذه من التجمع المرتب للرموز المتبقية.
ومن منظور التباديل، فإن \((c_{n-1},c_{n-2},\dots,c_0)\) هو شيفرة Lehmer للتبديل المطلوب. ولهذا لا تحتاج الطريقة إلى تجربة وتراجع؛ فكل خارج قسمة يثبت موضعًا نهائيًا، وكل باقٍ ينقل فقط الجزء غير المحلول إلى مستوى عاملي أصغر.
في المسألة الأصلية نحول أولًا الرتبة من 1-مفهرسة إلى 0-مفهرسة:
$$r=1{,}000{,}000-1=999{,}999.$$
وتوسعها في النظام العاملي هو
$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$$
إذن نختار على الترتيب العنصر رقم \(2\)، ثم \(6\)، ثم \(6\)، ثم \(2\)، ثم \(5\)، ثم \(1\)، ثم \(2\)، ثم \(1\)، ثم \(1\)، ثم \(0\) من بين العناصر المتبقية. وإذا بدأنا من المجموعة المرتبة \([0,1,2,3,4,5,6,7,8,9]\)، نحصل على
$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$$
ومن ثم يكون التبديل المعجمي رقم مليون هو
$$2783915460.$$
تتعامل تطبيقات C++ وPython وJava مع سلسلة من الرموز ومع رتبة تبديل 1-مفهرسة، ثم ترتب الرموز وتحسب \(n!\). وإذا كانت الرتبة المطلوبة خارج المجال \(1\le k\le n!\)، تتوقف العملية باعتبار الطلب غير صالح.
بعد ذلك تُحوَّل الرتبة إلى \(r=k-1\)، وتُحفظ الرموز المتبقية في حاوية مرتبة قابلة للحذف. وفي كل دورة تُقسَم \(r\) على \((m-1)!\)، ويُستعمل خارج القسمة فهرسًا لاختيار الرمز التالي، ثم يُضاف هذا الرمز إلى الناتج ويُحذف من الحاوية، بينما يصبح الباقي هو الرتبة الجديدة للمرحلة التالية.
كما تتضمن التطبيقات اختبارات صغيرة مثل أول وآخر تبديل للرموز \(0,1,2\). هذه الاختبارات تكشف بسرعة أي خطأ في اتجاه الترتيب أو في التحويل بين الفهرسة من 1 والفهرسة من 0.
يوجد \(n\) جولات اختيار. وفي هذه التطبيقات تُخزَّن الرموز المتبقية في قائمة بسيطة أو بنية شبيهة بالمصفوفة، لذا فإن حذف العنصر المختار يكلف \(O(n)\) في أسوأ الأحوال. وعليه يكون الزمن الكلي \(O(n^2)\)، بينما تكون الذاكرة الإضافية \(O(n)\).
بالنسبة إلى الحالة الأصلية حيث \(n=10\)، فهذه الكلفة صغيرة جدًا. المكسب الحقيقي هو أن الخوارزمية تبني التبديل المطلوب مباشرة بدل المرور على جميع \(10!\) تبديلًا ممكنًا.