# Total number of topological sorts

For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation.

Your task is to calculate the total number of topological sorts of a given DAG.

## Rules

• You can use any format to represent the graph, like adjacency matrix, adjacency list or edge list, as long as you don't do useful computations in your encoding. You can also have things like vertex count or vertex list in the input, if those are useful.
• You can assume the graph in the input is always a DAG (doesn't have any cycles).
• Your program should work in theory for any input. But it can fail if it overflows the basic integer type in your language.
• The names of vertices can be any consecutive values in any type. For example: numbers starting at 0 or 1. (And only if you are not storing code in this number, of course.)
• This is code-golf. Shortest code wins.

## Example

This is the same input in different formats. Your program don't have to accept all of them. Vertices are always integers starting at 0.

Adjacency list:
[ [1 2 3 5] [2 4] [] [2] [] [3] ]
[ [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] ]


It's the graph shown in this image:

The output should be:

9


The topological sorts are:

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

• Function? Whole Program? Either? Feb 18, 2015 at 22:38
• @isaacg Either. Feb 19, 2015 at 14:19

# Python, 58

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


The input consists of an adjacency dictionary G and a vertex set 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,6}


The code is recursive. The set V stores all nodes that still need visiting. For each potential next node, we check its suitability by seeing if no remaining vertices point to it, with V-G[v]==V checking that V and G[v] are disjoint. For all suitable such vertices, we add the number of topological sorts with it removed. As a base case, the empty set gives 1.

• +1 for not using edge list. Feb 19, 2015 at 14:40
• why is 6 missing from V? Apr 26, 2021 at 0:26

# Mathematica, 8057 51 bytes

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


Very straight-forward implementation of the definition. I'm just generating all permutations and count how many of them are valid. To check if a permutation is valid, I get all pairs of vertices in the permutation. Conveniently, Subsets[l,{2}] not only gives me all pairs, it also maintains the order they are found in in l - just what I need.

The above is a function that expects the vertex list and edge list, like

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


if you call the function f.

I'll try to golf this, or maybe use another approach later.

• Count[Permutations@#,l_/;Subsets@l~SubsetQ~#2]& Mar 8 at 3:40

# CJam - 25

q~{_f{1$-_j@j@&!*}_!+:+}j  With great help from user23013 :) Try it online Explanation: The general algorithm is the same as in xnor's Python solution. The key here is the j operator, which does memoized recursion. It takes a parameter, a value or array for the initial value(s) (as in f(0), f(1), etc) and a block to define the recursion. The j operator is used again inside the block for doing recursive (and memoized) calls to the same block. It can also be used with multiple parameters, but it's not the case here. user23013's great innovation is to use j with different data types, making use of the adjacency list as the array of initial values. 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(…)"

• Edited to explicitly allow vertex list in the input. Now 25 bytes. Feb 21, 2015 at 0:58
• @user23013 What kind of sorcery is this? :o Feb 21, 2015 at 9:05

# Nekomata + -n, 5 bytes

↕ᵚ{S=


Attempt This Online!

Takes input as a vertex count and a list of edges, e.g., 6 [[0,1],[0,2],[0,3],[0,5],[1,2],[1,4],[3,2],[5,3]].

↕ᵚ{S=
↕       Find a permutation of [0, ..., vertex count - 1]
ᵚ{     For each element in the edges list:
S        Find a subset of the permutation
=       that is equal to the edge


-n counts the number of solutions.

# Pyth, 27 bytes

Mlf!sm}_dHfq2lYyTfqSZUZ^UGG


Defines a 2 input function, g. First input is the number of vertices, second is the list of directed edges.

To test:

Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

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


Try it here.

• @user23013 Boht count and list are being used, in the expression ^UGG, which generates all G entry lists of range(len(G)). Feb 21, 2015 at 18:01
• I meant, will it be shorter if you use [0, 1, ...] directly in the input? Feb 21, 2015 at 22:49
• @user23013 No, it would be the same length: ^GlG vs. ^UGG. Feb 21, 2015 at 23:09

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


The input is the highest vertex number (starting with 0) and an edge list, where an edge is a two element list. Usage example: 5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]

How it works: count all permutations p of the vertices for which all edges [u,v] satisfy: position of u in p is less than position of v in p. That's a direct implementation of the definition.

Edit: my first version returned the topological sorts themselves and not how many there are. Fixed it.

Edit II: didn't work for graphs with not connected vertices. Fixed it.

• I'm thinking of adding a test case with only vertices but not edges... Feb 19, 2015 at 14:27
• @user23013: works for graphs with not connected vertices, now. It even became shorter.
– nimi
Feb 19, 2015 at 15:48

# Rust, 241 226 214 182 149 129 bytes

use itertools::*;fn f(n:usize,e:Vec<[usize;2]>)->usize{(0..n).permutations(n).filter(|p|e.iter().all(|&[i,j]|p[i]<p[j])).count()}


Try it online!

Rust port of this C++ answer. -20 thanks to @att. Slightly less golfed

use itertools::*;
fn f(n:usize,e:Vec<[usize;2]>)->usize{
(0..n).permutations(n).filter(|p|e.iter().all(|&[i,j]|p[i]<p[j])).count()
}

• 129 bytes
– att
Mar 24 at 1:45

# Rust, 607 bytes

Golfed version by @ceilingcat, greatly appreciated.

Try it online!

fn R()->Vec<i32>{let mut b=String::new();std::io::stdin().read_line(&mut b);b.trim().split(" ").map(|num|num.parse().expect("")).collect()}fn E(m:usize,N:&[i32],g:&[Vec<i32>],L:usize,D:&mut[i64],n:usize)->i64{if-1==D[m]{if m==L{D[m]=1}else{D[m]=0;for i in 0..n{if N[i]==0&&m&1<<i<1{let mut t=N.to_vec();for&v in&g[i]{t[v as usize]-=1}D[m]+=E(m|1<<i,&t,g,L,D,n)}}}}D[m]}fn main(){let f=R();let n=f[0]as usize;let(mut g,mut N,mut D)=(vec![vec![];n],vec![0;n],vec![-1;1<<n]);for _ in 0..f[1]{let I=R();let(u,v)=(I[0]-1,I[1]-1);g[u as usize].push(v);N[v as usize]+=1}println!("{}",E(0,&N,&g,(1<<n)-1,&mut D,n))}


Use the algorithm in @masked_huh's C++ code in the comment of this CodeForces post.

Ungolfed version. Attempt This Online!

use std::io;

let mut buffer = String::new();
buffer.trim().split_whitespace()
.map(|num| num.parse().expect("Failed to parse number"))
.collect()
}

fn rec(mask: i64, ind: &[i32], g: &[Vec<i32>], all_visited: i64, dp: &mut [i64], n: usize) -> i64 {
if dp[mask as usize] != -1 {
}
return 1;
}

let mut ans = 0;
for i in 0..n {
if ind[i] == 0 && (mask & (1 << i) == 0) {
let mut temp = ind.to_vec();
for &v in &g[i] {
temp[v as usize] -= 1;
}
ans += rec(mask | (1 << i), &temp, g, all_visited, dp, n);
}
}

ans
}

fn main() {
let (n, m) = (first_line[0] as usize, first_line[1]);

let mut g: Vec<Vec<i32>> = vec![vec![]; n];
let mut ind: Vec<i32> = vec![0; n];
let mut dp: Vec<i64> = vec![-1; 1 << n];
let all_visited: i64 = (1 << n) - 1;

for _ in 0..m {
let (mut u, mut v) = (line[0], line[1]);
u -= 1;
v -= 1;
g[u as usize].push(v);
ind[v as usize] += 1;
}

let ans = rec(0, &ind, &g, all_visited, &mut dp, n);

println!("{}", ans);
}


# JavaScript (Node.js), 74 bytes

f=(a,s=0,p)=>a.map(t=>s+=t&&!t.some(p=u=>a[u])&&f(a.map(u=>t!=u&&u)))|s+!p


Try it online!

• a: Input array. For recurse reason, false means used
• s: Sum to return
• p: active if unused elements exist

# C++ (gcc), 274 252 193 176 170 bytes

#import<regex>
int f(int n,int m,int*e,int*f){int V[n],c,d=n,i;for(;d--;)V[d]=d;do for(c=1,i=m;i--;)c*=V[e[i]]<V[f[i]];while(d-=c,std::next_permutation(V,V+n));return~d;}


Try it online!

This generates every permutation and filters out the invalid ones.

Slightly less golfed.

#import<regex>
int f(int n,int m,int*e,int*f){
int V[n],c,d=n,i;
for(;d--;)
V[d]=d;
do{
c=1;
for(i=m;i--;)
c*=V[e[i]]<V[f[i]];
d-=c;
}while(std::next_permutation(V,V+n));
return~d;
}