We are given fifty successful three-digit login attempts. In each attempt, the three digits appear in the same relative order as they do in the unknown passcode, but they need not be adjacent in the passcode itself. The goal is to recover the shortest passcode compatible with every observed attempt.
The implementations solve this by turning the keylog into an order relation on digits. Once that relation is known, the passcode is obtained by listing the digits in an order that respects every forced precedence constraint.
Let the attempts be \((a_i,b_i,c_i)\) for \(i=1,\dots,50\), and let \(V\subseteq\{0,1,\dots,9\}\) be the set of digits that appear anywhere in the keylog. We build a directed graph \(G=(V,E)\) whose edges express compulsory precedence relations between digits.
Each observed triple \(abc\) means exactly that \(a\) must appear before \(b\), and \(b\) must appear before \(c\). The implementations therefore insert the directed edges
$$a \to b,\qquad b \to c.$$
Nothing more is needed. The relation \(a\) before \(c\) is already implied by transitivity: if every valid passcode places \(a\) before \(b\) and \(b\) before \(c\), then it automatically places \(a\) before \(c\). So the code stores the immediate constraints and lets graph reachability represent the derived ones.
Because the digits are stored in sets, repeated appearances of the same precedence relation do not change the graph. The mathematical object is therefore a finite directed graph on the participating digits, not a multigraph weighted by frequency.
Write \(u \prec v\) if there is a directed path from \(u\) to \(v\) in \(G\). This reachability relation is the transitive closure of the recorded edges. When the keylog is consistent, it defines a partial order: some pairs of digits are forced into one order, while others may remain incomparable until more constraints are considered.
A candidate passcode \(P\) is valid exactly when every edge of \(G\) is respected by the left-to-right order inside \(P\). Indeed, if \(P\) respects every edge, then for each attempt \(abc\) we have \(a\) before \(b\) and \(b\) before \(c\), so \(abc\) occurs as a subsequence of \(P\). Conversely, any passcode containing every attempt as a subsequence must certainly respect all inserted edges. Thus the problem is equivalent to finding a linear extension of this partial order.
A topological ordering of \(G\) is a listing of the vertices in which every edge points from an earlier digit to a later one. By the previous observation, such an ordering is automatically a valid passcode.
It is also shortest in the model used by the implementations. Every digit in \(V\) must appear at least once, otherwise any login attempt containing that digit would be impossible. A topological order uses each participating digit exactly once, so its length is \(|V|\). No shorter string can exist, because a string of length less than \(|V|\) cannot even contain all distinct required digits.
So the problem is reduced to finding a topological ordering of \(G\).
The implementations use Kahn's algorithm. For a remaining vertex \(v\), let \(\operatorname{indeg}(v)\) be the number of incoming edges from vertices not yet written into the passcode. If \(\operatorname{indeg}(v)=0\), then no unresolved constraint forces another remaining digit to appear before \(v\). Such a vertex is safe to place next.
The key invariant is: after writing some prefix of the passcode and deleting those vertices together with their outgoing edges, the residual graph describes exactly the precedence constraints that still matter for the unfinished suffix. Therefore repeatedly removing a zero in-degree vertex preserves correctness.
If the residual graph ever has no zero in-degree vertex while digits remain, then there is a directed cycle and the data are inconsistent. If there is exactly one zero in-degree choice at every step, the passcode is uniquely determined. If several choices are available, then several shortest passcodes are compatible unless a tie-breaking rule is imposed.
The C++ implementation includes the miniature keylog
$$123,\qquad 135,\qquad 245.$$
Its vertex set is \(V=\{1,2,3,4,5\}\), and the directly stored edges are
$$1\to 2,\quad 2\to 3,\quad 1\to 3,\quad 3\to 5,\quad 2\to 4,\quad 4\to 5.$$
The initial in-degrees are
$$\operatorname{indeg}(1)=0,\ \operatorname{indeg}(2)=1,\ \operatorname{indeg}(3)=2,\ \operatorname{indeg}(4)=1,\ \operatorname{indeg}(5)=2.$$
So the first digit must be \(1\). After removing \(1\), digit \(2\) becomes available. After removing \(2\), both \(3\) and \(4\) have in-degree zero. That means the constraints no longer distinguish between those two positions. The ordered implementations choose the smaller available digit first, so they continue with \(3\), then \(4\), and finally \(5\), producing
$$12345.$$
This example illustrates both the mathematics and the implementation detail: the graph guarantees validity, and an ordered container makes the output deterministic when the partial order is not yet total.
The C++, Python, and Java implementations read each three-character attempt, mark its digits as present, and add directed edges only between consecutive positions in the attempt. Because adjacency sets are used, duplicate precedence relations are collapsed automatically.
Next, the implementations compute an in-degree count for every participating digit. Any digit with in-degree zero can be emitted immediately. After emitting such a digit, the implementation deletes its outgoing edges by decrementing the in-degrees of its successors; any successor whose count drops to zero becomes newly available.
This is exactly Kahn's topological-sort procedure. The C++ version keeps currently available digits in a min-priority queue. The Java version builds the graph with sorted digit sets and processes available digits through a queue. The Python version uses a deque and inserts outgoing neighbors in sorted order. All three are performing the same mathematical elimination process.
The digits are appended in the order they are removed. If the graph is acyclic and all participating digits are processed, the resulting string is a passcode consistent with every attempt. Because each digit is written once, the produced string is also shortest under this precedence-graph model.
Let \(A=50\) be the number of login attempts. Each attempt has length \(3\), so scanning the input takes \(O(A)\) time with tiny constants, and at most \(2A\) direct edges are inserted before deduplication. Since the vertices are decimal digits, we always have \(|V|\le 10\).
After the graph is built, Kahn's algorithm runs in \(O(|V|+|E|)\) time with a plain queue. The ordered extraction used by the C++ version changes this to \(O((|V|+|E|)\log |V|)\), but here \(|V|\le 10\), so the distinction is negligible. Memory usage is \(O(|V|+|E|)\).
Gegeben sind fünfzig erfolgreiche dreistellige Login-Versuche. In jedem Versuch erscheinen die drei Ziffern in derselben relativen Reihenfolge wie im unbekannten Passcode, aber nicht unbedingt direkt nebeneinander. Gesucht ist der kürzeste Passcode, der mit allen beobachteten Versuchen verträglich ist.
Die Implementierungen lösen das Problem, indem sie aus dem Keylog eine Ordnungsrelation auf den Ziffern erzeugen. Sobald diese Relation feststeht, erhält man den Passcode als Anordnung der Ziffern, die alle erzwungenen Vorher-Nachher-Beziehungen respektiert.
Bezeichne die Versuche mit \((a_i,b_i,c_i)\) für \(i=1,\dots,50\), und sei \(V\subseteq\{0,1,\dots,9\}\) die Menge aller Ziffern, die im Keylog vorkommen. Daraus konstruieren wir einen gerichteten Graphen \(G=(V,E)\), dessen Kanten zwingende Vorrangbeziehungen zwischen Ziffern darstellen.
Jedes beobachtete Tripel \(abc\) bedeutet: \(a\) muss vor \(b\) stehen und \(b\) muss vor \(c\) stehen. Deshalb tragen die Implementierungen genau die Kanten
$$a \to b,\qquad b \to c$$
ein. Mehr braucht man nicht. Die Beziehung \(a\) vor \(c\) folgt bereits transitiv: Wenn in jedem zulässigen Passcode \(a\) vor \(b\) und \(b\) vor \(c\) steht, dann steht automatisch auch \(a\) vor \(c\). Der Code speichert also nur die unmittelbaren Zwangsbedingungen; die abgeleiteten Bedingungen werden durch Erreichbarkeit im Graphen repräsentiert.
Da Mengenstrukturen verwendet werden, ändern wiederholte Vorkommen derselben Kante den Graphen nicht. Das mathematische Objekt ist somit ein endlicher gerichteter Graph auf den beteiligten Ziffern und kein gewichteter Multigraph.
Schreibe \(u \prec v\), wenn es in \(G\) einen gerichteten Pfad von \(u\) nach \(v\) gibt. Diese Erreichbarkeitsrelation ist die transitive Hülle der gespeicherten Kanten. Bei konsistenten Daten entsteht so eine Halbordnung: Manche Ziffern haben eine erzwungene Reihenfolge, andere bleiben zunächst unvergleichbar.
Ein Kandidat \(P\) ist genau dann ein gültiger Passcode, wenn \(P\) jede Kante von \(G\) in Leserichtung respektiert. Denn wenn \(P\) jede Kante respektiert, dann gilt für jedes Tripel \(abc\): \(a\) liegt vor \(b\) und \(b\) vor \(c\), also ist \(abc\) eine Teilfolge von \(P\). Umgekehrt muss jeder Passcode, der alle Versuche als Teilfolgen enthält, natürlich alle gespeicherten Kanten respektieren. Das Problem ist also äquivalent zur Bestimmung einer linearen Erweiterung dieser Halbordnung.
Eine topologische Ordnung von \(G\) ist eine Auflistung der Knoten, in der jede Kante von einer früheren zu einer späteren Ziffer zeigt. Nach der vorherigen Beobachtung ist eine solche Ordnung automatisch ein gültiger Passcode.
Sie ist im Modell der Implementierungen auch minimal. Jede Ziffer aus \(V\) muss mindestens einmal erscheinen; sonst wäre jeder Versuch, der diese Ziffer enthält, unmöglich. Eine topologische Ordnung verwendet jede beteiligte Ziffer genau einmal und hat daher Länge \(|V|\). Kürzer kann kein Passcode sein, weil eine Zeichenfolge mit weniger als \(|V|\) Positionen nicht einmal alle erforderlichen verschiedenen Ziffern enthalten kann.
Damit reduziert sich die Aufgabe darauf, eine topologische Ordnung von \(G\) zu finden.
Die Implementierungen verwenden Kahns Algorithmus. Für einen verbleibenden Knoten \(v\) sei \(\operatorname{indeg}(v)\) die Anzahl der eingehenden Kanten aus noch nicht ausgegebenen Ziffern. Gilt \(\operatorname{indeg}(v)=0\), dann zwingt keine offene Bedingung eine andere verbleibende Ziffer dazu, vor \(v\) zu stehen. Dann darf \(v\) als Nächstes geschrieben werden.
Die entscheidende Invariante lautet: Nachdem ein Präfix des Passcodes festgelegt und aus dem Graphen entfernt wurde, beschreibt der Restgraph genau die noch relevanten Vorrangbeziehungen für das verbleibende Suffix. Deshalb bleibt Korrektheit erhalten, wenn man wiederholt einen Knoten mit Eingangsgrad Null entfernt.
Falls der Restgraph noch Ziffern enthält, aber keinen solchen Knoten mehr besitzt, gibt es einen gerichteten Zyklus und die Daten wären widersprüchlich. Gibt es in jedem Schritt genau einen Knoten mit Eingangsgrad Null, dann ist der Passcode eindeutig bestimmt. Gibt es mehrere, dann existieren mehrere kürzeste Passcodes, sofern man keine Tie-Break-Regel vorgibt.
Die C++-Implementierung enthält das kleine Keylog
$$123,\qquad 135,\qquad 245.$$
Daraus ergibt sich \(V=\{1,2,3,4,5\}\) und die direkt gespeicherten Kanten
$$1\to 2,\quad 2\to 3,\quad 1\to 3,\quad 3\to 5,\quad 2\to 4,\quad 4\to 5.$$
Die anfänglichen Eingangsgrade sind
$$\operatorname{indeg}(1)=0,\ \operatorname{indeg}(2)=1,\ \operatorname{indeg}(3)=2,\ \operatorname{indeg}(4)=1,\ \operatorname{indeg}(5)=2.$$
Also muss zuerst \(1\) kommen. Nach dem Entfernen von \(1\) wird \(2\) verfügbar. Nach dem Entfernen von \(2\) haben sowohl \(3\) als auch \(4\) Eingangsgrad Null. Die Constraints unterscheiden diese beiden Positionen also nicht mehr. Die geordneten Implementierungen wählen dann die kleinere verfügbare Ziffer zuerst und erhalten
$$12345.$$
Das Beispiel zeigt beides: Der Graph garantiert die Gültigkeit, und ein geordneter Behälter macht die Ausgabe deterministisch, wenn die Halbordnung noch nicht total ist.
Die Implementierungen in C++, Python und Java lesen jeden dreistelligen Versuch ein, markieren die darin vorkommenden Ziffern und tragen gerichtete Kanten nur zwischen benachbarten Positionen des Versuchs ein. Da Nachbarschaftsmengen verwendet werden, werden doppelte Vorrangrelationen automatisch zusammengefasst.
Anschließend wird für jede beteiligte Ziffer der Eingangsgrad berechnet. Jede Ziffer mit Eingangsgrad Null kann sofort ausgegeben werden. Nach ihrer Ausgabe entfernt die Implementierung ihre ausgehenden Kanten, indem sie die Eingangsgrade der Nachfolger dekrementiert; fällt ein Nachfolger auf Null, wird er neu verfügbar.
Das ist genau Kahns topologische Sortierung. Die C++-Version verwendet dafür eine Min-Priority-Queue. Die Java-Version baut den Graphen mit sortierten Ziffernmengen auf und verarbeitet verfügbare Ziffern mit einer Queue. Die Python-Version nutzt eine Deque und fügt Nachfolger in sortierter Reihenfolge hinzu. Mathematisch ist es in allen drei Fällen derselbe Eliminationsprozess.
Die Ziffern werden in der Reihenfolge ihres Entfernens aneinandergehängt. Ist der Graph azyklisch und werden alle beteiligten Ziffern verarbeitet, entsteht eine Zeichenfolge, die mit jedem Login-Versuch verträglich ist. Weil jede Ziffer genau einmal geschrieben wird, ist diese Zeichenfolge im Präzedenzgraph-Modell zugleich kürzest.
Sei \(A=50\) die Anzahl der Login-Versuche. Jeder Versuch hat Länge \(3\), also kostet das Einlesen \(O(A)\) Zeit mit sehr kleinen Konstanten, und vor der Deduplizierung werden höchstens \(2A\) direkte Kanten eingefügt. Da die Knoten Dezimalziffern sind, gilt stets \(|V|\le 10\).
Nach dem Aufbau des Graphen läuft Kahns Algorithmus mit einer einfachen Queue in \(O(|V|+|E|)\). Die geordnete Auswahl der C++-Version ergibt \(O((|V|+|E|)\log |V|)\), aber bei \(|V|\le 10\) ist der Unterschied praktisch bedeutungslos. Der Speicherbedarf beträgt \(O(|V|+|E|)\).
Elimizde başarılı olmuş elli adet üç basamaklı giriş denemesi var. Her denemede görülen üç rakam, bilinmeyen şifrede aynı göreli sırayla yer alıyor; ancak şifrede yan yana durmaları gerekmiyor. Amaç, bütün denemelerle uyumlu olan en kısa şifreyi bulmaktır.
Uygulamalar bunu, denemelerden rakamlar üzerinde bir öncelik ilişkisi çıkararak çözüyor. Bu ilişki kurulduğunda şifre, bütün zorunlu önce-gelme koşullarını sağlayan bir rakam sıralaması haline geliyor.
Denemeleri \(i=1,\dots,50\) için \((a_i,b_i,c_i)\) ile gösterelim. Keylog içinde görünen tüm rakamların kümesi \(V\subseteq\{0,1,\dots,9\}\) olsun. Buradan, zorunlu sıralama ilişkilerini tutan yönlü bir \(G=(V,E)\) grafiği kuruyoruz.
Her \(abc\) üçlüsü, \(a\)'nın \(b\)'den önce, \(b\)'nin de \(c\)'den önce gelmesi gerektiğini söyler. Bu yüzden uygulamalar sadece şu kenarları ekler:
$$a \to b,\qquad b \to c.$$
Bundan fazlasına gerek yoktur. \(a\)'nın \(c\)'den önce gelmesi şartı zaten geçişlilikten doğar: her geçerli şifre \(a\)'yı \(b\)'den, \(b\)'yi de \(c\)'den önce yazıyorsa, doğal olarak \(a\) da \(c\)'den önce gelir. Yani kod yalnızca doğrudan kısıtları saklar; türetilen kısıtlar graf üzerindeki erişilebilirlik ile temsil edilir.
Kenarlar küme yapılarında tutulduğu için aynı ilişkinin tekrar görülmesi grafiği değiştirmez. Dolayısıyla matematiksel nesne, frekanslı bir çoklu graf değil, ilgili rakamlar üzerindeki sonlu bir yönlü graftır.
Eğer \(G\) içinde \(u\)'dan \(v\)'ye yönlü bir yol varsa \(u \prec v\) yazalım. Bu erişilebilirlik ilişkisi, kaydedilen kenarların geçişsel kapanışıdır. Veri tutarlıysa bu yapı bir kısmi sıra verir: bazı rakamların göreli yeri zorunludur, bazıları ise ek bilgi gelene kadar karşılaştırılamaz kalır.
Bir aday şifre \(P\), ancak ve ancak \(G\)'nin her kenarını soldan sağa doğru koruyorsa geçerlidir. Gerçekten de \(P\) bütün kenarları koruyorsa, her \(abc\) denemesi için \(a\) önce, sonra \(b\), sonra \(c\) gelir; dolayısıyla \(abc\), \(P\)'nin bir alt dizisidir. Tersi de açıktır: bütün denemeleri alt dizi olarak içeren bir şifre, eklenmiş bütün kenarları zorunlu olarak korumalıdır. Böylece problem, bu kısmi sıranın bir lineer uzantısını bulma problemine dönüşür.
\(G\)'nin topolojik sıralaması, her kenarın daha soldaki bir rakamdan daha sağdaki bir rakama baktığı bir düğüm listesi demektir. Bir önceki gözleme göre böyle bir sıralama otomatik olarak geçerli bir şifredir.
Aynı zamanda, uygulamaların kullandığı modelde bu şifre en kısadır. \(V\) kümesindeki her rakam en az bir kez görünmek zorundadır; aksi halde o rakamı içeren bir deneme karşılanamaz. Bir topolojik sıra, her katılan rakamı tam bir kez kullanır; dolayısıyla uzunluğu \(|V|\)'dir. \(|V|\)'den daha kısa bir dizge, gerekli bütün farklı rakamları bile içeremeyeceği için daha kısa bir çözüm mümkün değildir.
Yani problem, \(G\) grafiğinin bir topolojik sıralamasını bulmaya indirgenir.
Uygulamalar Kahn algoritmasını kullanır. Kalan bir \(v\) düğümü için \(\operatorname{indeg}(v)\), henüz şifreye yazılmamış düğümlerden gelen kenar sayısı olsun. Eğer \(\operatorname{indeg}(v)=0\) ise, kalan hiçbir kısıt başka bir rakamı \(v\)'den önce zorlamıyordur. Bu yüzden \(v\) sıradaki rakam olarak güvenle yazılabilir.
Temel invariant şudur: Şifrenin bir öneki yazılıp bu düğümler ile çıkan kenarları grafikten silindiğinde, geriye kalan grafik yalnızca henüz yazılmamış son ek için geçerli olan sıralama şartlarını taşır. Bu nedenle sıfır giriş dereceli bir düğümü tekrar tekrar kaldırmak doğruluğu bozmaz.
Eğer hâlâ rakam kaldığı halde sıfır giriş dereceli hiç düğüm yoksa, grafikte yönlü bir çevrim vardır ve veri çelişkilidir. Her adımda tam bir aday varsa şifre tektir. Aynı anda birden fazla aday varsa, ayrıca bir bağ-kırma kuralı koymadığınız sürece birden fazla en kısa şifre mümkündür.
C++ uygulamasındaki küçük kontrol verisi şudur:
$$123,\qquad 135,\qquad 245.$$
Burada \(V=\{1,2,3,4,5\}\) ve doğrudan kaydedilen kenarlar
$$1\to 2,\quad 2\to 3,\quad 1\to 3,\quad 3\to 5,\quad 2\to 4,\quad 4\to 5$$
olur. Başlangıç giriş dereceleri
$$\operatorname{indeg}(1)=0,\ \operatorname{indeg}(2)=1,\ \operatorname{indeg}(3)=2,\ \operatorname{indeg}(4)=1,\ \operatorname{indeg}(5)=2$$
şeklindedir. İlk rakam mecburen \(1\)'dir. \(1\) silinince \(2\) serbestleşir. \(2\) silinince bu kez hem \(3\) hem \(4\) sıfır giriş derecesine iner. Demek ki kısıtlar bu iki konumu artık birbirinden ayırmıyor. Sıralı veri yapısı kullanan uygulamalar küçük rakamı önce seçtiği için sonuç
$$12345$$
olur. Bu örnek hem matematiği hem de deterministik bağ-kırma davranışını gösterir.
C++, Python ve Java uygulamaları her üç basamaklı denemeyi okur, içindeki rakamları mevcut olarak işaretler ve yalnızca ardışık karakterler arasında yönlü kenarlar ekler. Komşuluk kümeleri kullanıldığı için yinelenen öncelik ilişkileri otomatik olarak tekilleşir.
Sonraki aşamada her rakam için giriş derecesi hesaplanır. Giriş derecesi sıfır olan herhangi bir rakam hemen çıktıya eklenebilir. Bir rakam eklendikten sonra onun çıkış kenarları kaldırılır; bunun için ardıllarının giriş dereceleri azaltılır. Derecesi sıfıra düşen her ardıl yeni aday haline gelir.
Bu tam olarak Kahn topolojik sıralamasıdır. C++ sürümü kullanılabilir rakamları min-öncelik kuyruğunda tutar. Java sürümü grafiği sıralı rakam kümeleriyle kurar ve adayları kuyrukla işler. Python sürümü bir deque kullanır ve çıkan komşuları sıralı olarak ekler. Matematiksel olarak üçü de aynı eleme sürecini yürütür.
Rakamlar, grafikten çıkarıldıkları sırayla yan yana eklenir. Grafik çevrimsizse ve bütün ilgili rakamlar işlenirse, elde edilen dizge her giriş denemesiyle uyumludur. Her rakam yalnızca bir kez yazıldığı için bu dizge, öncelik-graf modeli altında aynı zamanda en kısa şifredir.
\(A=50\) giriş denemesi olsun. Her deneme uzunluğu \(3\) olduğu için girdi taraması çok küçük sabitlerle \(O(A)\) zamanda yapılır; tekilleştirme öncesinde en fazla \(2A\) doğrudan kenar eklenir. Düğümler onluk rakamlar olduğundan \(|V|\le 10\) her zaman geçerlidir.
Graf kurulduktan sonra Kahn algoritması basit kuyrukla \(O(|V|+|E|)\) zamanda çalışır. C++ sürümündeki sıralı seçim bunu \(O((|V|+|E|)\log |V|)\) biçimine getirir, fakat \(|V|\le 10\) olduğundan pratik fark yoktur. Bellek kullanımı \(O(|V|+|E|)\)'dir.
Se nos dan cincuenta intentos correctos de acceso de tres dígitos. En cada intento, los tres dígitos aparecen en el mismo orden relativo que en la clave secreta, aunque no tienen por qué ser consecutivos dentro de ella. La tarea es reconstruir la clave más corta compatible con todos los intentos observados.
Las implementaciones convierten el registro de accesos en una relación de precedencia entre dígitos. Una vez fijada esa relación, la clave se obtiene como una ordenación de los dígitos que respeta todas las restricciones obligatorias.
Denotemos los intentos por \((a_i,b_i,c_i)\) para \(i=1,\dots,50\), y sea \(V\subseteq\{0,1,\dots,9\}\) el conjunto de dígitos que aparecen en el registro. Construimos un grafo dirigido \(G=(V,E)\) cuyas aristas expresan relaciones forzadas de anterioridad.
Cada triple observado \(abc\) significa que \(a\) debe ir antes que \(b\), y \(b\) antes que \(c\). Por eso las implementaciones insertan exactamente las aristas
$$a \to b,\qquad b \to c.$$
No hace falta añadir más. La condición \(a\) antes que \(c\) ya queda implicada por transitividad: si toda clave válida coloca \(a\) antes que \(b\) y \(b\) antes que \(c\), entonces necesariamente coloca \(a\) antes que \(c\). El código almacena solo las restricciones inmediatas; las consecuencias derivadas aparecen como alcanzabilidad en el grafo.
Como las aristas se guardan en conjuntos, repetir la misma relación de precedencia no modifica el grafo. El objeto matemático real es, por tanto, un grafo dirigido finito sobre los dígitos participantes, no un multigrafo ponderado por frecuencias.
Escribamos \(u \prec v\) si existe un camino dirigido de \(u\) a \(v\) en \(G\). Esta relación de alcanzabilidad es el cierre transitivo de las aristas almacenadas. Cuando el registro es consistente, define un orden parcial: algunos pares de dígitos quedan totalmente determinados y otros permanecen incomparables hasta que intervienen más restricciones.
Una clave candidata \(P\) es válida si y solo si respeta cada arista de \(G\) de izquierda a derecha. En efecto, si \(P\) respeta todas las aristas, entonces para cada intento \(abc\) se cumple que \(a\) aparece antes que \(b\) y \(b\) antes que \(c\), de modo que \(abc\) es una subsecuencia de \(P\). A la inversa, cualquier clave que contenga todos los intentos como subsecuencias debe respetar necesariamente todas las aristas insertadas. Así, el problema equivale a encontrar una extensión lineal de este orden parcial.
Un orden topológico de \(G\) es una lista de vértices en la que cada arista apunta de un dígito anterior a otro posterior. Por la observación anterior, tal orden es automáticamente una clave válida.
Además, en el modelo usado por las implementaciones, también es mínima. Cada dígito de \(V\) debe aparecer al menos una vez; de lo contrario, cualquier intento que lo contenga sería imposible. Un orden topológico usa cada dígito participante exactamente una vez, así que su longitud es \(|V|\). No puede existir una cadena más corta, porque una cadena con menos de \(|V|\) posiciones ni siquiera podría contener todos los dígitos distintos necesarios.
En consecuencia, el problema se reduce a encontrar un orden topológico de \(G\).
Las implementaciones usan el algoritmo de Kahn. Para un vértice restante \(v\), sea \(\operatorname{indeg}(v)\) el número de aristas entrantes procedentes de vértices que todavía no se han escrito en la clave. Si \(\operatorname{indeg}(v)=0\), entonces ninguna restricción pendiente obliga a colocar otro dígito restante antes que \(v\). Por eso puede emitirse con seguridad como siguiente carácter.
El invariante central es este: después de escribir un prefijo de la clave y borrar esos vértices junto con sus aristas salientes, el grafo residual describe exactamente las restricciones que aún afectan al sufijo pendiente. Por tanto, eliminar repetidamente un vértice de grado de entrada cero preserva la corrección.
Si alguna vez quedan dígitos pero ya no existe ningún vértice con grado de entrada cero, entonces hay un ciclo dirigido y los datos serían inconsistentes. Si en cada paso existe exactamente uno, la clave queda determinada de forma única. Si hay varios a la vez, entonces existen varias claves mínimas compatibles, salvo que se imponga una regla de desempate.
La implementación en C++ incluye el pequeño registro
$$123,\qquad 135,\qquad 245.$$
Su conjunto de vértices es \(V=\{1,2,3,4,5\}\), y las aristas almacenadas directamente son
$$1\to 2,\quad 2\to 3,\quad 1\to 3,\quad 3\to 5,\quad 2\to 4,\quad 4\to 5.$$
Los grados de entrada iniciales son
$$\operatorname{indeg}(1)=0,\ \operatorname{indeg}(2)=1,\ \operatorname{indeg}(3)=2,\ \operatorname{indeg}(4)=1,\ \operatorname{indeg}(5)=2.$$
Así que el primer dígito debe ser \(1\). Tras eliminar \(1\), queda disponible \(2\). Tras eliminar \(2\), tanto \(3\) como \(4\) pasan a tener grado de entrada cero. Eso significa que las restricciones ya no distinguen entre esas dos posiciones. Las versiones ordenadas eligen antes el dígito menor, continúan con \(3\), luego \(4\), y terminan en
$$12345.$$
El ejemplo muestra simultáneamente la idea matemática y el comportamiento determinista de la implementación cuando el orden parcial todavía no es total.
Las implementaciones en C++, Python y Java leen cada intento de tres caracteres, marcan sus dígitos como presentes e insertan aristas dirigidas solo entre posiciones consecutivas del intento. Como las listas de adyacencia se almacenan en conjuntos, las relaciones repetidas se colapsan automáticamente.
Después se calcula el grado de entrada de cada dígito participante. Cualquier dígito con grado de entrada cero puede emitirse de inmediato. Al emitirlo, la implementación elimina sus aristas salientes decrementando el grado de entrada de sus sucesores; todo sucesor cuyo grado cae a cero pasa a estar disponible.
Eso es exactamente la ordenación topológica de Kahn. La versión en C++ mantiene los dígitos disponibles en una cola de prioridad mínima. La versión en Java construye el grafo con conjuntos ordenados y procesa los disponibles con una cola. La versión en Python usa una deque y añade los sucesores en orden creciente. Matemáticamente, las tres realizan la misma eliminación.
Los dígitos se concatenan en el orden en que salen del grafo. Si el grafo es acíclico y se procesan todos los dígitos participantes, la cadena resultante es una clave compatible con todos los intentos. Como cada dígito se escribe una sola vez, la cadena también es mínima dentro de este modelo de grafo de precedencias.
Sea \(A=50\) el número de intentos. Como cada intento tiene longitud \(3\), leer la entrada cuesta \(O(A)\) tiempo con constantes diminutas, y antes de deduplicar se insertan a lo sumo \(2A\) aristas directas. Dado que los vértices son dígitos decimales, siempre se cumple \(|V|\le 10\).
Una vez construido el grafo, el algoritmo de Kahn corre en \(O(|V|+|E|)\) con una cola simple. La extracción ordenada usada en C++ lo convierte en \(O((|V|+|E|)\log |V|)\), pero con \(|V|\le 10\) la diferencia es despreciable. La memoria usada es \(O(|V|+|E|)\).
题目给出五十次成功的三位登录尝试。每一次尝试中的三个数字，都按照它们在真正密码中的相对先后顺序出现，但不要求在密码里相邻。目标是找出与全部尝试都相容的最短密码。
三个实现的核心思想完全一致：先把这些尝试转换成数字之间的先后约束，再输出一个满足所有约束的数字排列。这个排列本身就是密码。
把五十条记录记为 \((a_i,b_i,c_i)\)，其中 \(i=1,\dots,50\)。设 \(V\subseteq\{0,1,\dots,9\}\) 是所有在记录中出现过的数字集合。我们构造一个有向图 \(G=(V,E)\)，图中的边表示“某个数字必须先于另一个数字出现”。
一条记录 \(abc\) 的含义是：在真正的密码中，\(a\) 必须在 \(b\) 之前，\(b\) 必须在 \(c\) 之前。因此实现中只加入两条直接边
$$a \to b,\qquad b \to c.$$
不需要显式加入 \(a \to c\)。原因很简单：如果每个合法密码都满足 \(a\) 在 \(b\) 之前、\(b\) 在 \(c\) 之前，那么 \(a\) 必然也在 \(c\) 之前。也就是说，代码只保存最直接的约束，而由这些约束推出的更长链式关系，则通过图上的可达性来表达。
由于邻接关系使用集合存储，同一条约束边即使在多条记录中重复出现，也只会被保留一次。所以这里真正研究的数学对象，是参与数字构成的一个有限有向图，而不是带重复边的多重图。
如果在图 \(G\) 中存在一条从 \(u\) 到 \(v\) 的有向路径，就记作 \(u \prec v\)。这个关系正是直接约束边的传递闭包。只要数据本身是自洽的，它就定义了一个偏序：某些数字之间的先后关系被完全确定，某些数字则可能暂时不可比较。
一个候选密码 \(P\) 当且仅当它按从左到右的顺序尊重图中的每一条边时才是合法的。证明并不复杂。如果 \(P\) 尊重所有边，那么对每一条记录 \(abc\)，我们都有 \(a\) 在 \(b\) 之前、\(b\) 在 \(c\) 之前，所以 \(abc\) 一定是 \(P\) 的一个子序列。反过来，如果某个密码把所有记录都包含为子序列，那么它当然不可能违反任何一条直接边。因此，题目等价于求这个偏序的一个线性扩张。
图 \(G\) 的一个拓扑序，是指把所有顶点排成一列，使得每条边都从更靠左的数字指向更靠右的数字。根据上面的论证，任何拓扑序都会自动给出一个合法密码。
更重要的是，在这三个实现所采用的模型中，这样得到的密码还是最短的。集合 \(V\) 中的每个数字至少要出现一次，否则包含该数字的登录记录根本无法匹配。另一方面，一个拓扑序恰好把每个参与数字写一次，所以它的长度正好是 \(|V|\)。长度少于 \(|V|\) 的字符串甚至无法容纳所有必须出现的不同数字，因此不可能更短。
于是问题就被压缩为：求图 \(G\) 的一个拓扑排序。
三个实现都使用 Kahn 的拓扑排序思想。对剩余顶点 \(v\)，记 \(\operatorname{indeg}(v)\) 为来自“尚未写入密码”的顶点的入边条数。如果 \(\operatorname{indeg}(v)=0\)，就说明当前还没有任何未解决的约束要求别的剩余数字必须放在 \(v\) 前面，所以 \(v\) 可以安全地作为下一个数字输出。
关键不变式是：当我们已经写出密码的一个前缀，并从图中删除这些顶点及其所有出边后，剩下的图恰好刻画了尚未完成部分仍然需要满足的全部先后关系。因此，反复删除零入度顶点不会破坏正确性。
如果还有顶点未处理，但图中已经不存在零入度顶点，那就意味着出现了有向环，数据彼此矛盾。若每一步都只有一个零入度顶点，则答案唯一；若某一步同时出现多个零入度顶点，则说明当前偏序还没有完全变成全序，此时会存在多个同样短的合法密码，除非实现另外规定了一个固定的选取顺序。
C++ 实现里带有一个小型校验数据：
$$123,\qquad 135,\qquad 245.$$
此时顶点集为 \(V=\{1,2,3,4,5\}\)，直接存储的边是
$$1\to 2,\quad 2\to 3,\quad 1\to 3,\quad 3\to 5,\quad 2\to 4,\quad 4\to 5.$$
初始入度分别为
$$\operatorname{indeg}(1)=0,\ \operatorname{indeg}(2)=1,\ \operatorname{indeg}(3)=2,\ \operatorname{indeg}(4)=1,\ \operatorname{indeg}(5)=2.$$
所以第一位只能是 \(1\)。删去 \(1\) 之后，\(2\) 变成零入度；再删去 \(2\) 之后，\(3\) 和 \(4\) 同时变成零入度。也就是说，到这一步为止，约束已经无法区分它们两者谁先谁后。带有有序容器的实现会优先选择较小的那个数字，于是继续输出 \(3\)、再输出 \(4\)、最后输出 \(5\)，得到
$$12345.$$
这个例子很有用，因为它同时说明了两件事：图结构保证了答案合法，而有序的数据结构则在偏序尚未完全定序时提供了确定性的输出。
C++、Python 和 Java 实现都会逐条读取三位记录，先把出现过的数字加入顶点集合，再只对记录中的相邻位置加入有向边。由于邻接表使用集合，重复出现的同一约束边会自动去重。
接下来，代码统计每个参与数字的入度。任何入度为零的数字都可以立即写入结果。写出一个数字后，就把它指向的出边删除，具体做法是把后继顶点的入度减一；一旦某个后继的入度降为零，它就进入可选集合。
这正是 Kahn 算法。C++ 版本用最小优先队列维护当前可写数字；Java 版本在构图时就使用有序集合，再用队列推进；Python 版本使用 deque，并把后继按升序加入。虽然容器细节不同，但底层数学过程完全一致。
所有数字按照被移出图的顺序依次连接成字符串。只要图无环且所有参与数字都被处理完，得到的字符串就与全部登录记录相容。因为每个数字只写一次，所以它也是这种先后约束模型下的最短密码。
设登录记录条数为 \(A=50\)。每条记录长度都是 \(3\)，因此读入与建图只需 \(O(A)\) 时间，常数非常小；去重之前至多插入 \(2A\) 条直接边。由于顶点只是十进制数字，所以始终有 \(|V|\le 10\)。
图建好之后，若用普通队列执行 Kahn 算法，时间复杂度是 \(O(|V|+|E|)\)。C++ 版本因为使用有序提取，写成 \(O((|V|+|E|)\log |V|)\) 也可以，但在 \(|V|\le 10\) 的前提下这点差异几乎没有实际意义。空间复杂度为 \(O(|V|+|E|)\)。
Даны пятьдесят успешных трёхзначных попыток входа. В каждой попытке три цифры стоят в том же относительном порядке, что и в настоящем пароле, хотя вовсе не обязаны идти подряд. Нужно восстановить кратчайший пароль, согласующийся со всеми наблюдениями.
Все три реализации сводят задачу к порядку предшествования между цифрами. После этого пароль получается как последовательность цифр, которая удовлетворяет всем обязательным отношениям «раньше-позже».
Обозначим попытки через \((a_i,b_i,c_i)\) для \(i=1,\dots,50\), а через \(V\subseteq\{0,1,\dots,9\}\) обозначим множество всех цифр, встречающихся в журнале. Построим ориентированный граф \(G=(V,E)\), где ребро означает обязательное отношение порядка между двумя цифрами.
Каждая запись \(abc\) утверждает, что \(a\) должна стоять раньше \(b\), а \(b\) раньше \(c\). Поэтому реализации добавляют только рёбра
$$a \to b,\qquad b \to c.$$
Явно добавлять \(a \to c\) не требуется. Это условие уже следует из транзитивности: если любой допустимый пароль ставит \(a\) раньше \(b\) и \(b\) раньше \(c\), то автоматически \(a\) оказывается раньше \(c\). Значит, код хранит только непосредственные ограничения, а все производные соотношения выражаются достижимостью в графе.
Поскольку соседние вершины хранятся в множествах, повторное появление одной и той же зависимости не меняет граф. Следовательно, математически здесь возникает конечный ориентированный граф на участвующих цифрах, а не мультиграф с кратными рёбрами.
Будем писать \(u \prec v\), если в графе \(G\) существует ориентированный путь из \(u\) в \(v\). Это отношение достижимости и есть транзитивное замыкание записанных рёбер. Если данные согласованы, оно задаёт частичный порядок: для некоторых пар цифр порядок жёстко определён, а некоторые пары могут оставаться несравнимыми.
Кандидатный пароль \(P\) является корректным тогда и только тогда, когда он уважает каждое ребро графа слева направо. Действительно, если \(P\) уважает все рёбра, то для любой записи \(abc\) цифра \(a\) стоит раньше \(b\), а \(b\) раньше \(c\), то есть \(abc\) является подпоследовательностью \(P\). Обратное тоже верно: любой пароль, содержащий все попытки как подпоследовательности, обязан удовлетворять всем добавленным рёбрам. Значит, задача эквивалентна поиску линейного расширения этого частичного порядка.
Топологическая сортировка графа \(G\) — это такой порядок вершин, в котором каждое ребро идёт от более ранней цифры к более поздней. Из предыдущего пункта следует, что любой такой порядок автоматически задаёт корректный пароль.
Более того, в модели, используемой реализациями, он ещё и кратчайший. Каждая цифра из \(V\) должна появиться хотя бы один раз; иначе любая запись с этой цифрой была бы невозможна. Топологический порядок использует каждую участвующую цифру ровно один раз, поэтому его длина равна \(|V|\). Более короткой строки быть не может: строка длины меньше \(|V|\) даже не способна вместить все обязательные различные цифры.
Тем самым задача сводится к поиску топологического порядка графа \(G\).
Реализации используют алгоритм Кана. Для оставшейся вершины \(v\) обозначим через \(\operatorname{indeg}(v)\) число входящих рёбер из ещё не выписанных цифр. Если \(\operatorname{indeg}(v)=0\), то никакое неразрешённое ограничение не заставляет ставить другую оставшуюся цифру перед \(v\). Значит, \(v\) можно безопасно поставить следующей.
Главный инвариант таков: после того как мы выписали некоторый префикс пароля и удалили соответствующие вершины вместе с исходящими рёбрами, оставшийся граф описывает в точности те ограничения порядка, которые ещё важны для недописанного суффикса. Поэтому последовательное удаление вершины с нулевой входной степенью сохраняет корректность.
Если вершины ещё остались, но ни одной с нулевой входной степенью нет, значит, возник ориентированный цикл и данные противоречивы. Если на каждом шаге такая вершина ровно одна, пароль определяется однозначно. Если их несколько, то без дополнительного правила выбора существует несколько кратчайших совместимых паролей.
В реализации на C++ есть маленький проверочный журнал
$$123,\qquad 135,\qquad 245.$$
Здесь \(V=\{1,2,3,4,5\}\), а непосредственно сохранённые рёбра равны
$$1\to 2,\quad 2\to 3,\quad 1\to 3,\quad 3\to 5,\quad 2\to 4,\quad 4\to 5.$$
Начальные входные степени таковы:
$$\operatorname{indeg}(1)=0,\ \operatorname{indeg}(2)=1,\ \operatorname{indeg}(3)=2,\ \operatorname{indeg}(4)=1,\ \operatorname{indeg}(5)=2.$$
Значит, первой обязана идти цифра \(1\). После её удаления доступной становится \(2\). После удаления \(2\) нулевую входную степень одновременно получают \(3\) и \(4\). Это означает, что ограничения уже не различают эти две позиции. Упорядоченные реализации выбирают меньшую доступную цифру раньше, поэтому продолжают с \(3\), затем \(4\), и получают
$$12345.$$
Этот пример полезен тем, что одновременно демонстрирует математическую модель и детерминированный выбор в ситуации, когда частичный порядок ещё не стал полным.
Реализации на C++, Python и Java читают каждую трёхсимвольную запись, отмечают встречающиеся цифры и добавляют ориентированные рёбра только между соседними позициями в записи. Поскольку списки смежности основаны на множествах, повторяющиеся зависимости автоматически схлопываются.
Затем вычисляется входная степень каждой участвующей цифры. Любую цифру с нулевой входной степенью можно немедленно выписать в ответ. После этого её исходящие рёбра удаляются, то есть входные степени её потомков уменьшаются; как только у потомка степень становится нулевой, он становится доступным.
Это и есть алгоритм Кана. Версия на C++ хранит доступные цифры в минимальной очереди с приоритетом. Версия на Java строит граф на отсортированных множествах и использует очередь. Версия на Python работает с deque и добавляет потомков в отсортированном порядке. Математически все три версии выполняют одну и ту же процедуру исключения.
Цифры конкатенируются в том порядке, в котором они удаляются из графа. Если граф ацикличен и все участвующие цифры обработаны, полученная строка согласуется со всеми попытками входа. Поскольку каждая цифра записывается только один раз, эта строка также является кратчайшим паролем в рамках модели графа предшествования.
Пусть \(A=50\) — число попыток входа. Каждая попытка имеет длину \(3\), так что чтение и построение графа занимают \(O(A)\) времени с очень маленькими константами; до устранения повторов добавляется не более \(2A\) прямых рёбер. Так как вершины — это десятичные цифры, всегда выполняется \(|V|\le 10\).
После построения графа алгоритм Кана работает за \(O(|V|+|E|)\) с обычной очередью. Упорядоченное извлечение в версии на C++ даёт оценку \(O((|V|+|E|)\log |V|)\), но при \(|V|\le 10\) эта разница практически незаметна. Память: \(O(|V|+|E|)\).
لدينا خمسون محاولة دخول ناجحة مكوّنة من ثلاثة أرقام. في كل محاولة تظهر الأرقام الثلاثة بالترتيب النسبي نفسه الذي تظهر به داخل رمز المرور الحقيقي، لكن ليس من الضروري أن تكون متجاورة داخله. المطلوب هو استنتاج أقصر رمز مرور ينسجم مع جميع هذه المحاولات.
جوهر الحل في اللغات الثلاث واحد: نحول السجل إلى علاقة أسبقية بين الأرقام، ثم نستخرج ترتيبًا للأرقام يحقق كل القيود المفروضة. هذا الترتيب نفسه هو رمز المرور المطلوب.
لنرمز إلى المحاولات بالثلاثيات \((a_i,b_i,c_i)\) حيث \(i=1,\dots,50\)، ولتكن \(V\subseteq\{0,1,\dots,9\}\) مجموعة كل الأرقام التي تظهر في السجل. نبني منها رسمًا بيانيًا موجهًا \(G=(V,E)\) تمثل حوافه علاقات السبق الإلزامية بين الأرقام.
كل ثلاثية \(abc\) تعني أن \(a\) يجب أن يسبق \(b\)، وأن \(b\) يجب أن يسبق \(c\). لذلك تضيف التطبيقات الحافتين المباشرتين فقط
$$a \to b,\qquad b \to c.$$
ولا حاجة إلى إضافة \(a \to c\) صراحة. فهذه العلاقة تأتي تلقائيًا من خاصية التعدي: إذا كان كل رمز مرور صالح يضع \(a\) قبل \(b\) و\(b\) قبل \(c\)، فلا بد أن يضع \(a\) قبل \(c\) أيضًا. لهذا يخزن الكود القيود المباشرة فقط، بينما تمثل قابلية الوصول داخل الرسم البياني كل القيود المشتقة.
وبما أن الحواف تُخزن داخل مجموعات، فإن تكرار القيد نفسه في أكثر من سطر لا يغير الرسم البياني. إذًا الكائن الرياضي الحقيقي هنا هو رسم بياني موجه منتهٍ على الأرقام المشاركة، وليس رسمًا متعدد الحواف مع أوزان تكرارية.
نكتب \(u \prec v\) إذا وُجد في \(G\) مسار موجه من \(u\) إلى \(v\). هذه العلاقة هي الإغلاق التعدي للحواف المسجلة. وعندما تكون البيانات منسجمة، فإنها تعطي ترتيبًا جزئيًا: بعض الأزواج من الأرقام يُفرض ترتيبها بشكل قاطع، وبعضها يبقى غير قابل للمقارنة إلى أن تضيف القيود معلومات إضافية.
يكون رمز المرور المرشح \(P\) صالحًا إذا وفقط إذا احترم كل حافة في \(G\) عند القراءة من اليسار إلى اليمين. فالسبب واضح: إذا احترم \(P\) جميع الحواف، فلكل محاولة \(abc\) سنجد أن \(a\) يظهر قبل \(b\) و\(b\) قبل \(c\)، وبالتالي تكون \(abc\) سلسلة فرعية من \(P\). والعكس صحيح أيضًا: أي رمز مرور يحتوي كل المحاولات كسلاسل فرعية لا يمكنه أن يخالف أي حافة أضيفت إلى الرسم. لذلك تصبح المسألة مكافئة لإيجاد امتداد خطي لهذا الترتيب الجزئي.
الترتيب الطوبولوجي للرسم \(G\) هو قائمة للرؤوس بحيث تشير كل حافة من رقم يظهر أبكر إلى رقم يظهر لاحقًا. وبحسب الفقرة السابقة، فإن أي ترتيب من هذا النوع يعطي تلقائيًا رمز مرور صالحًا.
وهو أيضًا الأقصر ضمن النموذج الذي تستعمله التطبيقات. فكل رقم في المجموعة \(V\) يجب أن يظهر مرة واحدة على الأقل، وإلا فإن أي محاولة تحتوي هذا الرقم ستصبح مستحيلة. ومن جهة أخرى، الترتيب الطوبولوجي يكتب كل رقم مشارك مرة واحدة فقط، لذا يكون طوله \(|V|\). ولا يمكن أن يوجد رمز أقصر من ذلك، لأن سلسلة طولها أقل من \(|V|\) لا تستطيع حتى أن تحتوي جميع الأرقام المختلفة المطلوبة.
وهكذا تختزل المسألة إلى إيجاد ترتيب طوبولوجي للرسم \(G\).
تعتمد التطبيقات على خوارزمية كاهن. ولأي رأس متبقٍ \(v\)، نعرّف \(\operatorname{indeg}(v)\) بأنه عدد الحواف الداخلة إليه من رؤوس لم تُكتب بعد في رمز المرور. إذا تحقق \(\operatorname{indeg}(v)=0\)، فهذا يعني أنه لا توجد أي قيود غير محلولة تفرض رقمًا آخر متبقيًا قبل \(v\). لذلك يمكن وضع \(v\) بأمان في الموضع التالي.
الثابت الأساسي هو الآتي: بعد أن نكتب بادئة من رمز المرور ونحذف رؤوسها مع حوافها الخارجة، فإن الرسم المتبقي يصف بدقة القيود التي ما زالت تؤثر في اللاحقة غير المكتملة. ولهذا فإن حذف رأس ذي درجة داخلة صفرية مرة بعد مرة يحافظ على الصحة.
إذا بقيت أرقام غير مكتوبة ولكن لم يعد هناك أي رأس بدرجة داخلة صفرية، فهذا يعني وجود دورة موجهة وأن البيانات متناقضة. وإذا وُجد رأس واحد فقط في كل خطوة فالحل فريد. أما إذا وُجد أكثر من رأس متاح في اللحظة نفسها، فهناك عدة رموز مرور دنيا متوافقة ما لم نفرض قاعدة كسر تعادل محددة.
تحتوي نسخة C++ على مثال فحص صغير هو
$$123,\qquad 135,\qquad 245.$$
هنا تكون مجموعة الرؤوس \(V=\{1,2,3,4,5\}\)، والحواف المخزنة مباشرة هي
$$1\to 2,\quad 2\to 3,\quad 1\to 3,\quad 3\to 5,\quad 2\to 4,\quad 4\to 5.$$
أما الدرجات الداخلة الابتدائية فهي
$$\operatorname{indeg}(1)=0,\ \operatorname{indeg}(2)=1,\ \operatorname{indeg}(3)=2,\ \operatorname{indeg}(4)=1,\ \operatorname{indeg}(5)=2.$$
إذن لا بد أن يبدأ الترتيب بالرقم \(1\). وبعد حذف \(1\) يصبح \(2\) متاحًا. وبعد حذف \(2\) يصبح كل من \(3\) و\(4\) ذا درجة داخلة صفرية. وهذا يعني أن القيود لم تعد تميز بين هذين الموضعين. الإصدارات التي تستخدم بنية مرتبة تختار الرقم الأصغر أولًا، فتتابع بـ \(3\) ثم \(4\) ثم \(5\)، وتحصل على
$$12345.$$
هذا المثال يوضح في وقت واحد البنية الرياضية وآلية الخرج الحتمي عندما لا يكون الترتيب الجزئي قد تحول بعد إلى ترتيب كلي.
تقرأ تطبيقات C++ وPython وJava كل محاولة ثلاثية، وتضيف الأرقام الظاهرة إلى مجموعة الرؤوس، ثم تضيف حوافًا موجهة بين المواضع المتجاورة فقط داخل المحاولة. وبما أن الجوار يُخزن داخل مجموعات، فإن العلاقات المكررة تُدمج تلقائيًا.
بعد ذلك يُحسب عدد الحواف الداخلة لكل رقم مشارك. أي رقم درجته الداخلة صفر يمكن إخراجه فورًا. وعند إخراجه تُحذف حوافه الخارجة، أي تُنقص الدرجات الداخلة لخلفائه؛ وكل خلف يصل إلى الصفر يصبح متاحًا للمعالجة.
وهذا هو بالضبط الفرز الطوبولوجي بطريقة كاهن. تستخدم نسخة C++ طابور أولوية صاعدًا للاحتفاظ بالأرقام المتاحة. وتبني نسخة Java الرسم البياني باستعمال مجموعات مرتبة ثم تعالج المتاح بطابور. أما نسخة Python فتستخدم deque وتضيف الخلفاء بترتيب تصاعدي. وعلى الرغم من اختلاف الحاويات، فالعملية الرياضية واحدة في الحالات الثلاث.
تُلصق الأرقام بحسب ترتيب خروجها من الرسم البياني. إذا كان الرسم خاليًا من الدورات وعولجت جميع الأرقام المشاركة، فإن السلسلة الناتجة توافق كل محاولات الدخول. ولأن كل رقم يكتب مرة واحدة فقط، فهي أيضًا أقصر سلسلة ممكنة ضمن نموذج رسم الأسبقية.
لنفرض أن عدد المحاولات هو \(A=50\). بما أن طول كل محاولة يساوي \(3\)، فإن قراءة البيانات وبناء الرسم يتمان بزمن \(O(A)\) مع ثوابت صغيرة جدًا، ويُضاف قبل إزالة التكرار ما لا يزيد على \(2A\) من الحواف المباشرة. وبما أن الرؤوس مجرد أرقام عشرية، فلدينا دائمًا \(|V|\le 10\).
بعد بناء الرسم يعمل خوارزم كاهن بزمن \(O(|V|+|E|)\) إذا استُخدم طابور عادي. أما الاستخراج المرتب في نسخة C++ فيعطي \(O((|V|+|E|)\log |V|)\)، لكن بما أن \(|V|\le 10\) فالفارق العملي مهمل. الذاكرة المطلوبة هي \(O(|V|+|E|)\).