Skip to content

Instantly share code, notes, and snippets.

@galenseilis
Last active March 29, 2024 09:28
Show Gist options
  • Save galenseilis/1bd1893f01ed729185c2fc4a0dff49cd to your computer and use it in GitHub Desktop.
Save galenseilis/1bd1893f01ed729185c2fc4a0dff49cd to your computer and use it in GitHub Desktop.
from math import comb
# Implementation of DAG counter
def dagcount(n):
a = {}
a[0] = 1
for h in range(1,n+1):
a[h] = 0
for k in range(1,h+1):
a[h] += (-1)**(k+1) * comb(h,k) * 2**(k*(h-k)) * a[h-k]
return a
# True results
y_true = [
1,
1,
3,
25,
543,
29281,
3781503,
1138779265,
783702329343,
1213442454842881,
4175098976430598143,
31603459396418917607425,
521939651343829405020504063,
18676600744432035186664816926721,
1439428141044398334941790719839535103
]
# Predictions
y_pred = dagcount(len(y_true))
# Check predictions against reference
for i in range(len(y_true)):
print(y_true[i] == y_pred[i])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment