16
\$\begingroup\$

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

It's the graph shown in this image:

Example graph

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]
\$\endgroup\$
2
  • \$\begingroup\$ Function? Whole Program? Either? \$\endgroup\$
    – isaacg
    Commented Feb 18, 2015 at 22:38
  • \$\begingroup\$ @isaacg Either. \$\endgroup\$
    – jimmy23013
    Commented Feb 19, 2015 at 14:19

10 Answers 10

7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ +1 for not using edge list. \$\endgroup\$
    – jimmy23013
    Commented Feb 19, 2015 at 14:40
  • \$\begingroup\$ why is 6 missing from V? \$\endgroup\$
    – Zombo
    Commented Apr 26, 2021 at 0:26
5
\$\begingroup\$

Mathematica, 80 57 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.

\$\endgroup\$
1
  • \$\begingroup\$ Count[Permutations@#,l_/;Subsets@l~SubsetQ~#2]& \$\endgroup\$
    – alephalpha
    Commented Mar 8 at 3:40
4
\$\begingroup\$

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(…)"
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Edited to explicitly allow vertex list in the input. Now 25 bytes. \$\endgroup\$
    – jimmy23013
    Commented Feb 21, 2015 at 0:58
  • \$\begingroup\$ @user23013 What kind of sorcery is this? :o \$\endgroup\$ Commented Feb 21, 2015 at 9:05
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

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

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

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.

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

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()
}
\$\endgroup\$
1
  • \$\begingroup\$ 129 bytes \$\endgroup\$
    – att
    Commented Mar 24 at 1:45
0
\$\begingroup\$

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;

fn read_ints() -> Vec<i32> {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).expect("Failed to read line");
    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 dp[mask as usize];
    }
    if mask == all_visited {
        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);
        }
    }

    dp[mask as usize] = ans;
    ans
}

fn main() {
    let first_line = read_ints();
    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 line = read_ints();
        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);
}
\$\endgroup\$
0
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.