Für eine gegebene DAG (gerichteter azyklischer Graph) ist jede ihrer topologischen Sortierungen eine Permutation aller Eckpunkte, wobei für jede Kante (u, v) in der DAG u vor v in der Permutation erscheint.

Ihre Aufgabe ist es, die Gesamtzahl der topologischen Sorten einer bestimmten DAG zu berechnen.

Regeln

• Sie können ein beliebiges Format verwenden, um das Diagramm darzustellen, z. B. die Adjazenzmatrix, die Adjazenzliste oder die Kantenliste, sofern Sie in Ihrer Codierung keine nützlichen Berechnungen durchführen. Sie können auch Dinge wie die Anzahl der Scheitelpunkte oder die Scheitelpunktliste in der Eingabe haben, wenn diese nützlich sind.
• Sie können davon ausgehen, dass das Diagramm in der Eingabe immer eine DAG ist (keine Zyklen).
• Ihr Programm sollte theoretisch für jede Eingabe funktionieren. Es kann jedoch fehlschlagen, wenn der grundlegende Ganzzahltyp in Ihrer Sprache überläuft.
• Die Namen von Scheitelpunkten können beliebige aufeinanderfolgende Werte in einem beliebigen Typ sein. Zum Beispiel: Zahlen, die bei 0 oder 1 beginnen. (Und natürlich nur, wenn Sie keinen Code in dieser Zahl speichern.)
• Das ist Code-Golf. Der kürzeste Code gewinnt.

Beispiel

Dies ist die gleiche Eingabe in verschiedenen Formaten. Ihr Programm muss nicht alle akzeptieren. Scheitelpunkte sind immer ganze Zahlen, die bei 0 beginnen.

Adjacency list:
[ [1 2 3 5] [2 4] [] [2] [] [3] ]
Adjacency matrix:
[ [0 1 1 1 0 1] [0 0 1 0 1 0] [0 0 0 0 0 0] [0 0 1 0 0 0] [0 0 0 0 0 0] [0 0 0 1 0 0] ]
Edge list:
6 [ [0 1] [0 2] [0 3] [0 5] [1 2] [1 4] [3 2] [5 3] ]

Es ist die Grafik in diesem Bild:

Die Ausgabe sollte sein:

9

Die topologischen Sorten sind:

[0 1 4 5 3 2]
[0 1 5 4 3 2]
[0 1 5 3 4 2]
[0 1 5 3 2 4]
[0 5 1 4 3 2]
[0 5 1 3 4 2]
[0 5 1 3 2 4]
[0 5 3 1 4 2]
[0 5 3 1 2 4]

CJam - 25

q~{_f{1$-_j@j@&!*}_!+:+}j

Mit großer Hilfe von user23013 :)

Probieren Sie es online aus

Erläuterung:

Der allgemeine Algorithmus ist der gleiche wie in der Python-Lösung von xnor .
Der Schlüssel hier ist der jOperator, der die gespeicherte Rekursion ausführt. Für die Definition der Rekursion sind ein Parameter, ein Wert oder ein Array für die Anfangswert (e) (wie in f (0), f (1) usw.) und ein Block erforderlich. Der jOperator wird innerhalb des Blocks erneut verwendet, um rekursive (und gespeicherte) Aufrufe an denselben Block auszuführen. Es kann auch mit mehreren Parametern verwendet werden, ist hier jedoch nicht der Fall.
Die große Innovation von user23013 besteht darin, j mit verschiedenen Datentypen zu verwenden und dabei die Adjazenzliste als Array von Anfangswerten zu verwenden.

q~             read and evaluate the input (vertex list followed by adjacency list)
{…}j           run the block on the vertex list, doing memoized recursion
                and using the adjacency list for initial values
    _          copy the vertex list
    f{…}       for each vertex and the vertex list
        1$-    copy the vertex and remove it from the list
                Python: "V-{v}"
        _j     copy the reduced list and call the j block recursively
                this solves the problem for the reduced vertex list
                Python: "f(G,V-{v})"
        @j     bring the vertex to the top of the stack and call the j block recursively
                in this case, it's called with a vertex rather than a list
                and the memoized value is instantly found in the list of initial values
                effectively, this gets the list of vertices adjacent to the current vertex
                Python: "G[v]"
        @&     bring the reduced list to the top of the stack and intersect
        !*     multiply the number of topological sorts of the reduced vertex list
                with 1 if the intersection was empty and 0 if not
                Python: equivalent to "*(V-G[v]==V)"
               after this loop we get an array of sub-results for the reduced vertex lists
    _!+        add 1 or 0 to the array if the array was empty or not
                because we want to get 1 for the empty array
                Python: equivalent to "V<{0}or"
    :+         add the numbers in the array
                Python: "sum(…)"

Python, 58

f=lambda G,V:V<{0}or sum(f(G,V-{v})*(V-G[v]==V)for v in V)

Die Eingabe besteht aus einem Adjazenzwörterbuch Gund einem Scheitelpunktsatz V.

G = {0:{1,2,3,5}, 1:{2,4}, 2:set(), 3:{2}, 4:set(), 5:{3}, 6:set()}
V = {0,1,2,3,4,5}

Der Code ist rekursiv. Das Set Vspeichert alle Knoten, die noch besucht werden müssen. Für jeden potenziellen nächsten Knoten überprüfen wir seine Eignung, indem wir prüfen, ob keine verbleibenden Scheitelpunkte darauf zeigen, V-G[v]==Vindem wir dies überprüfen Vund G[v]disjunkt sind. Für alle geeigneten solchen Eckpunkte addieren wir die Anzahl der topologischen Sortierungen, wobei sie entfernt wurden. Als Basisfall ergibt die leere Menge 1.

Mathematica, 80 57 51 Bytes

Count[Permutations@#,l_/;l~Subsets~{2}~SubsetQ~#2]&

Sehr einfache Umsetzung der Definition. Ich generiere nur alle Permutationen und zähle, wie viele davon gültig sind. Um zu überprüfen, ob eine Permutation gültig ist, erhalte ich alle Eckpunktpaare in der Permutation. Praktischerweise Subsets[l,{2}]gibt es mir nicht nur alle Paare, sondern behält auch die Reihenfolge bei, in der sie sich befinden l- genau das, was ich brauche.

Das Obige ist eine Funktion, die die Scheitelpunktliste und die Kantenliste wie erwartet erwartet

f[{1, 2, 3, 4, 5, 6}, {{1, 2}, {1, 3}, {1, 4}, {1, 6}, {2, 3}, {2, 5}, {4, 3}, {6, 4}}]

wenn Sie die Funktion aufrufen f.

Ich werde versuchen, dies zu spielen, oder später einen anderen Ansatz verwenden.

Pyth, 27 Bytes

Mlf!sm}_dHfq2lYyTfqSZUZ^UGG

Definiert eine 2 Eingabefunktion , g. Die erste Eingabe ist die Anzahl der Eckpunkte, die zweite die Liste der gerichteten Kanten.

Zu testen:

Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

Input:
6, [ [0, 1], [0, 2], [0, 3], [0, 5], [1, 2], [1, 4], [3, 2], [5, 3] ]

Probieren Sie es hier aus.

Haskell, 102 107 100 89 85 Bytes

import Data.List
(%)=elemIndex
n#l=sum[1|p<-permutations[0..n],and[u%p<v%p|[u,v]<-l]]

Die Eingabe ist die höchste Scheitelpunktnummer (beginnend mit 0) und eine Kantenliste, wobei eine Kante eine Liste mit zwei Elementen ist. Anwendungsbeispiel:5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]

So funktioniert es: Zählen Sie alle Permutationen pder Eckpunkte, für die alle Kanten [u,v]erfüllt sind: Die Position von uin pist kleiner als die Position von vin p. Das ist eine direkte Implementierung der Definition.

Bearbeiten: Meine erste Version hat die topologischen Sortierungen selbst zurückgegeben und nicht, wie viele es gibt. Behoben.

Bearbeiten II: funktionierte nicht für Diagramme mit nicht verbundenen Scheitelpunkten. Behoben.