Tor
Sortieren Sie eine Liste von Elementen, um sicherzustellen, dass jedes Element nach den angegebenen Abhängigkeiten aufgelistet wird.
Eingang
Ein Array von Arrays von Ganzzahlen, wobei jede Ganzzahl den auf 0 oder 1 basierenden Index eines anderen Elements angibt, nach dem dieses Element kommen muss. Die Eingabe kann ein Array oder eine Zeichenfolge oder alles andere sein, was für den Menschen lesbar ist.
Zum Beispiel eine 0-basierte Eingabe:
[
[ 2 ], // item 0 comes after item 2
[ 0, 3 ], // item 1 comes after item 0 and 3
[ ], // item 2 comes anywhere
[ 2 ] // item 3 comes after item 2
]
Angenommen, es gibt keine zirkulären Abhängigkeiten, es gibt immer mindestens eine gültige Reihenfolge.
Ausgabe
Die Zahlen in Abhängigkeitsreihenfolge. Eine mehrdeutige Reihenfolge muss nicht deterministisch sein. Die Ausgabe kann ein Array oder ein Text oder etwas anderes sein, das von Menschen gelesen werden kann.
In der Ausgabe sollte nur eine Bestellung angegeben werden, auch wenn es mehrere gültige Bestellungen gibt.
Mögliche Ausgaben für die obigen Eingaben sind:
[ 2, 3, 0, 1 ]
[ 2, 0, 3, 1 ]
Wertung
Eine Funktion oder ein Programm, das dies in der geringsten Anzahl von Bytes abschließt, gewinnt den Ruhm der Akzeptanz. Die Frist ist in 6 Tagen.
Antworten:
Gelee, 8 Bytes
Dies basiert auf dem (nicht implementierten) Tiefenansatz von @ xnors Python-Antwort .
Probieren Sie es online!
Wie es funktioniert
quelle
Pyth, 21 Bytes
Prüfung:
quelle
Python 2, 73 Bytes
Sortiert die Eckpunkte nach der Anzahl ihrer Nachkommen, die
f
rekursiv berechnet wird. Wenn ein Scheitelpunkt auf einen anderen Scheitelpunkt zeigt, enthalten seine Nachkommen den spitzen Scheitelpunkt und alle Nachkommen dieses Scheitelpunkts, sodass er streng mehr Nachkommen hat. Es wird also wie gewünscht später als der spitze Eckpunkt in der Reihenfolge platziert.Die Anzahl der Nachkommen eines Scheitelpunkts ist eine für sich und die Anzahl der Nachkommen jedes seiner untergeordneten Elemente. Beachten Sie, dass ein Nachkomme mehrfach gezählt werden kann, wenn mehrere Pfade zu ihm führen.
Es hätte auch funktioniert, die Tiefe zu verwenden, anstatt die Anzahl der Nachkommen zu bestimmen
außer das
max
müsste man0
auf eine leere liste geben.quelle
Pyth, 19 Bytes
Probieren Sie es online aus: Demonstration
Erläuterung:
quelle
Bash, 35 Bytes
Beispiellauf
I / O ist 1-indiziert. Jedes Array wird in einer separaten Zeile mit Leerzeichen als Elementtrennzeichen angezeigt.
Wie es funktioniert
tsort
- was ich in der Antwort von @ DigitalTrauma erfahren habe - liest durch Leerzeichen getrennte Tokenpaare, die auf eine Teilreihenfolge hinweisen, und gibt eine Gesamtreihenfolge (in Form einer sortierten Liste aller eindeutigen Token) aus, die die oben genannte Teilreihenfolge erweitert.Allen Zahlen in einer bestimmten Zeile folgt entweder ein Leerzeichen oder ein Zeilenvorschub. Der
s/\s/ $. /g
Teil des Perl-Befehls ersetzt diese Leerzeichen durch ein Leerzeichen, die Zeilennummer und ein anderes Leerzeichen, wodurch sichergestellt wird, dass jedes n in der Zeile k vor k steht .Wenn die Zeile leer ist (dh nur aus einem
s/^$/ /
Zeilenumbruch besteht), wird ihr ein Leerzeichen vorangestellt. Auf diese Weise verwandelt die zweite Ersetzung eine leere Zeile k ink k
, wobei sichergestellt wird, dass jede Ganzzahl mindestens einmal in der Zeichenfolge vorkommt, zu der eine Pipeline geleitet wirdtsort
.quelle
tsort
besser / schneller gegriffen als ich :) Danke für die zusätzliche Erklärung.Bash + Coreutils,
2080Eingabe als durch Leerzeichen getrennte Zeilen, zB:
nl
Fügt allen Zeilen nullbasierte Indizes hinzused
Teilt Abhängigkeitslisten in einfache Abhängigkeitspaare auf und macht unvollständige Abhängigkeiten von sich selbst abhängig.tsort
führt die erforderliche topologische Sortierung durchtac
Die Ausgabe erfolgt in umgekehrter ReihenfolgeIdeone. Ideone mit @Dennis 'Testfall
quelle
Python 2,
143118116 BytesEin etwas zufälligerer Ansatz.
Bearbeitungen:
quelle