Untuk DAG yang diberikan (grafik asiklik terarah), masing-masing jenis topologisnya adalah permutasi dari semua simpul, di mana untuk setiap tepi (u, v) dalam DAG, u muncul sebelum v dalam permutasi.

Tugas Anda adalah untuk menghitung jumlah total jenis topologi DAG yang diberikan.

Aturan

• Anda dapat menggunakan format apa pun untuk mewakili grafik, seperti matriks adjacency, daftar adjacency atau daftar tepi, selama Anda tidak melakukan perhitungan yang berguna dalam pengkodean Anda. Anda juga dapat memiliki hal-hal seperti jumlah titik atau daftar titik dalam input, jika itu berguna.
• Anda dapat mengasumsikan grafik dalam input selalu DAG (tidak memiliki siklus).
• Program Anda harus bekerja secara teori untuk masukan apa pun. Tetapi itu bisa gagal jika melimpahi tipe integer dasar dalam bahasa Anda.
• Nama simpul dapat berupa nilai berurutan dalam jenis apa pun. Misalnya: angka mulai dari 0 atau 1. (Dan hanya jika Anda tidak menyimpan kode dalam angka ini, tentu saja.)
• Ini adalah kode-golf. Kode terpendek menang.

Contoh

Ini adalah input yang sama dalam berbagai format. Program Anda tidak harus menerima semuanya. Verteks selalu bilangan bulat mulai dari 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] ]

Ini adalah grafik yang ditunjukkan pada gambar ini:

Outputnya harus:

9

Jenis topologi adalah:

[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

Dengan bantuan besar dari user23013 :)

Cobalah online

Penjelasan:

Algoritma umum sama dengan dalam solusi Python xnor .
Kuncinya di sini adalah joperator, yang melakukan rekursi memoised. Dibutuhkan parameter, nilai atau larik untuk nilai awal (seperti dalam f (0), f (1), dll) dan blok untuk menentukan rekursi. The joperator digunakan lagi di dalam blok untuk melakukan panggilan rekursif (dan memoized) ke blok yang sama. Ini juga dapat digunakan dengan beberapa parameter, tetapi tidak demikian halnya di sini.
inovasi hebat user23013 adalah menggunakan j dengan tipe data yang berbeda, menggunakan daftar kedekatan sebagai array nilai awal.

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)

Input terdiri dari kamus kedekatan Gdan satu set simpul 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}

Kode ini bersifat rekursif. Set Vmenyimpan semua node yang masih perlu dikunjungi. Untuk setiap simpul potensial berikutnya, kami memeriksa kesesuaiannya dengan melihat apakah tidak ada simpul yang tersisa menunjuk ke sana, dengan V-G[v]==Vmemeriksa itu Vdan G[v]terpisah. Untuk semua simpul yang cocok, kami menambahkan jumlah jenis topologi dengan itu dihapus. Sebagai kasing, set kosong memberi 1.

Mathematica, 80 57 51 byte

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

Implementasi definisi yang sangat mudah. Saya hanya menghasilkan semua permutasi dan menghitung berapa banyak dari mereka yang valid. Untuk memeriksa apakah permutasi valid, saya mendapatkan semua pasangan simpul dalam permutasi. Nyaman, Subsets[l,{2}]tidak hanya memberi saya semua pasangan, itu juga mempertahankan urutan mereka ditemukan l- hanya apa yang saya butuhkan.

Di atas adalah fungsi yang mengharapkan daftar titik dan tepi, seperti

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

jika Anda memanggil fungsi f.

Saya akan mencoba bermain golf ini, atau mungkin menggunakan pendekatan lain nanti.

Pyth, 27 byte

Mlf!sm}_dHfq2lYyTfqSZUZ^UGG

Menentukan fungsi input 2 g,. Input pertama adalah jumlah simpul, kedua adalah daftar tepi terarah.

Untuk mengetes:

Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

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

Coba di sini.

Haskell, 102 107 100 89 85 byte

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

Input adalah nomor titik tertinggi (dimulai dengan 0) dan daftar tepi, di mana ujung adalah daftar dua elemen. Contoh penggunaan:5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]

Cara kerjanya: hitung semua permutasi pdari simpul yang [u,v]memuaskan semua sisi : posisi uin plebih kecil dari posisi vin p. Itu implementasi langsung dari definisi.

Sunting: versi pertama saya mengembalikan jenis topologi sendiri dan tidak berapa banyak. Memperbaikinya.

Sunting II: tidak berfungsi untuk grafik dengan simpul yang tidak terhubung. Memperbaikinya.