Coverage for partitionsets/partition.py: 100.00%

50 statements  

« prev     ^ index     » next       coverage.py v7.4.1, created at 2024-02-04 22:17 +0100

1#! /usr/bin/env python 

2""" Minimal implementation of a partitioning class for sets based 

3on [PartImplPy] and feedback from [PyLint, Flake8]. 

4 

5All python sources are licensed under the MIT License. 

6As entry point for further research cf. [PartOfASet_WP] 

7 

8References: 

9 

10[Flake8]: https://pypi.python.org/pypi/flake8 

11 

12[PartImplPy]: http://code.activestate.com/recipes/577211/ (r1) 

13 

14[PartOfASet_WP]: Wikipedia entry Partition_of_a_set at 

15 http://en.wikipedia.org/wiki/Partition_of_a_set 

16 

17[PyLint]: https://pypi.python.org/pypi/pylint 

18 

19 

20""" 

21from __future__ import print_function 

22 

23from collections import defaultdict 

24 

25 

26class Partition: 

27 """Sets of only a few items already have many ways they can be partitioned 

28 into subsets. Therefore it can be useful to generate these partitions by 

29 index, like the partition class were some large list where one can just 

30 access element "i". Of course one should not compute the whole list in 

31 advance but compute the partitions on the fly. This recipe was originally 

32 extracted form a book by Kreher and Stinson. Over the years I came back to 

33 my code from time to time creating a new and hopefully more pythonic 

34 version each time I understood it better. My current take on it is that the 

35 algorithm looks a lot like creating a Pascals triangle in order to compute 

36 combinations. One just tries to find a way down the triangle to a specific 

37 element, each time subtracting the amounts the different positions in the 

38 triangle account for. It is also similar to finding indexed permutations of 

39 a set with elements occurring more than once. One of these days I will 

40 perhaps understand how all of this fits together. Until then I'll post code 

41 solving specific situations. cf. [PartImplPy]""" 

42 

43 def __init__(self, ordered_set): 

44 self.data = list(ordered_set) 

45 self.n_data = len(ordered_set) 

46 self.table = self.rgf_table() 

47 

48 def __getitem__(self, i): 

49 """Generates set partitions by index""" 

50 if i > len(self) - 1: 

51 raise IndexError 

52 a_list = self.unrank_rgf(i) 

53 result = self.as_set_partition(a_list) 

54 return result 

55 

56 def __len__(self): 

57 return self.table[self.n_data, 0] 

58 

59 def __delitem__(self, index): 

60 pass 

61 

62 def __setitem__(self, key, value): 

63 pass 

64 

65 def as_set_partition(self, a_list): 

66 """Transform a restricted growth function into a partition""" 

67 n_list = max(a_list[1:] + [1]) 

68 n_data = self.n_data 

69 data = self.data 

70 partition = [[] for _ in range(n_list)] 

71 for i in range(n_data): 

72 partition[a_list[i + 1] - 1].append(data[i]) 

73 return partition 

74 

75 def rgf_table(self): 

76 """Compute the table values, but: The key line in the algorithm is 

77 D[i,j] = j * D[i-1,j] + D[i-1,j+1] which identifies D[i,j] as the 

78 number of ways to add i new items to a partition that already has 

79 j blocks. So e.g. D[1, j] = j+1 because a new 

80 item can be added to a partition having j blocks by adding it to any 

81 existing block or by having it start its own new block. Thus D[i,0] is 

82 the number of ways to partition the set {1, ..., i}. 

83 

84 To solve this problem for combinations (i.e. get the i-th subset of a 

85 set), just take the binary representation of the index i, right? The 

86 places where 1's occur tell you which items to keep -- no need to 

87 generate Pascal's triangle""" 

88 n_data = self.n_data 

89 a_dict = defaultdict(lambda: 1) 

90 for i in range(1, n_data + 1): 

91 for j in range(0, n_data - i + 1): 

92 a_dict[i, j] = j * a_dict[i - 1, j] + a_dict[i - 1, j + 1] 

93 return a_dict 

94 

95 def unrank_rgf(self, r_saught): 

96 """Unrank a restricted growth function""" 

97 n_data = self.n_data 

98 a_list = [1 for _ in range(n_data + 1)] 

99 j = 1 

100 a_dict = self.table 

101 for i in range(2, n_data + 1): 

102 v_j = a_dict[n_data - i, j] 

103 cr_j = j * v_j 

104 if cr_j <= r_saught: 

105 a_list[i] = j + 1 

106 r_saught -= cr_j 

107 j += 1 

108 else: 

109 a_list[i] = r_saught // v_j + 1 

110 r_saught %= v_j 

111 return a_list