Dla danego DAG (ukierunkowanego wykresu acyklicznego) każdy z jego rodzajów topologicznych jest permutacją wszystkich wierzchołków, gdzie dla każdej krawędzi (u, v) w DAG u występuje przed v w permutacji.

Twoim zadaniem jest obliczenie całkowitej liczby rodzajów topologicznych danego DAG.

Zasady

• Możesz użyć dowolnego formatu do przedstawienia wykresu, takiego jak macierz przylegania, lista przylegania lub lista krawędzi, o ile nie wykonasz przydatnych obliczeń w kodowaniu. Na wejściu można także umieścić takie elementy, jak liczba wierzchołków lub lista wierzchołków, jeśli są one przydatne.
• Możesz założyć, że wykres na wejściu jest zawsze DAG (nie ma żadnych cykli).
• Twój program powinien działać teoretycznie dla każdego wejścia. Ale może się nie powieść, jeśli przepełni podstawowy typ liczb całkowitych w twoim języku.
• Nazwy wierzchołków mogą być dowolnymi kolejnymi wartościami dowolnego typu. Na przykład: liczby zaczynające się od 0 lub 1. (I oczywiście tylko wtedy, gdy nie zapisujesz kodu w tym numerze).
• To jest golf golfowy. Najkrótszy kod wygrywa.

Przykład

To samo wejście w różnych formatach. Twój program nie musi akceptować wszystkich. Wierzchołki są zawsze liczbami całkowitymi zaczynającymi się od 0.

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] ]

Jest to wykres pokazany na tym obrazku:

Dane wyjściowe powinny być:

9

Rodzaje topologiczne to:

[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

Z wielką pomocą od user23013 :)

Wypróbuj online

Wyjaśnienie:

Ogólny algorytm jest taki sam jak w rozwiązaniu Python firmy xnor .
Kluczem jest tutaj joperator, który dokonuje zapamiętywania rekurencji. Pobiera parametr, wartość lub tablicę dla wartości początkowych (jak w f (0), f (1) itd.) I blok do zdefiniowania rekurencji. jOperator jest ponownie wykorzystywane wewnątrz bloku robi rekurencyjnych (i memoized) połączenia do tego samego bloku. Można go również używać z wieloma parametrami, ale tutaj tak nie jest.
Wielką innowacją użytkownika user23013 jest użycie j z różnymi typami danych, wykorzystując listę sąsiedztwa jako tablicę wartości początkowych.

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)

Dane wejściowe składają się ze słownika przylegania Gi zestawu wierzchołkówV .

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}

Kod jest rekurencyjny. Zestaw Vprzechowuje wszystkie węzły, które nadal wymagają odwiedzin. Dla każdego potencjalnego następnego węzła sprawdzamy jego przydatność, sprawdzając, czy żadne pozostałe wierzchołki nie wskazują na niego, V-G[v]==Vsprawdzając to Vi czy G[v]są rozłączne. Dla wszystkich odpowiednich takich wierzchołków dodajemy liczbę rodzajów topologicznych po usunięciu. W podstawowym przypadku pusty zestaw daje 1.

Mathematica, 80 57 51 bajtów

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

Bardzo proste wdrożenie definicji. Właśnie generuję wszystkie permutacje i liczę, ile z nich jest poprawnych. Aby sprawdzić, czy permutacja jest poprawna, otrzymuję wszystkie pary wierzchołków w permutacji. Dogodnie Subsets[l,{2}]nie tylko daje mi wszystkie pary, ale także utrzymuje porządek, w którym się znajdują l- dokładnie to, czego potrzebuję.

Powyżej jest funkcja, która oczekuje listy wierzchołków i listy krawędzi, jak

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

jeśli wywołasz funkcję f.

Spróbuję zagrać w golfa, a może później zastosuję inne podejście.

Pyth, 27 bajtów

Mlf!sm}_dHfq2lYyTfqSZUZ^UGG

Definiuje funkcję 2 wejść, g . Pierwsze wejście to liczba wierzchołków, drugie to lista skierowanych krawędzi.

Testować:

Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

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

Wypróbuj tutaj.

Haskell, 102 107 100 89 85 bajtów

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

Dane wejściowe to najwyższa liczba wierzchołków (zaczynająca się od 0) i lista krawędzi, gdzie krawędź jest listą dwóch elementów. Przykład użycia:5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]

Jak to działa: policz wszystkie permutacje pwierzchołków, dla których [u,v]spełniają wszystkie krawędzie : pozycja uin pjest mniejsza niż pozycja vin p. To bezpośrednie wdrożenie definicji.

Edycja: moja pierwsza wersja zwróciła same rodzaje topologiczne, a nie ich liczbę. Naprawione.

Edycja II: nie działał dla wykresów z niepołączonymi wierzchołkami. Naprawione.