Coverage for causalspyne/poset_approach.py: 92%

1 

2"""Generate ground truth pair (D, A_S), where D is a DAG and A is the 

3optimal abstraction of D with respect to score S (e.g. BIC, AIC score). 

4 

5Given D, construct the poset of graphical abstractions and perform 

6exhaustive search for the optimal abstraction. This will be a useful 

7ground truth for evaluating a greedy algorithm that avoids learning D 

8and directly learns A_S via greedy search from the top of the lattice. 

9 

10We can start in the observational setting at first and then move to 

11the interventional setting later. 

12""" 

13 

14from typing import Generator, List 

15 

16 

17def partitions(n: int) -> Generator[List[List[int]], None, None]: 

18 """Enumerate all partitions of n labelled objects. 

19 

20 The number of partitions is given by the Bell number, B_n. See 

21 https://en.wikipedia.org/wiki/Partition_of_a_set#Counting_partitions 

22 

23 Make sure to memoize this first if we plan to call it many times! 

24 """ 

25 if n == 1: 

26 yield [[1]] 

27 else: 

28 for partition in partitions(n - 1): 

29 yield partition + [[n]] 

30 for idx, part in enumerate(partition): 

31 prepart = partition[:idx] 

32 postpart = partition[idx + 1:] 

33 yield prepart + [part + [n]] + postpart 

34 

35 

36def abstractions(partial_order) -> Generator[List, None, None]: 

37 """Enumerate partitions that are consistent with the given partial 

38 order.""" 

39 yield None