如何快速计算集合集合所有交点的包含顺序 [英] How to compute fast the containment order of all intersections of a collection of sets
问题描述
我有一个整数有限集Ai的有限集合A = {A1，... Ak}，我想在Python中计算以下内容:
I have a finite collection A = {A1,...Ak} of finite sets Ai of integers and I want to compute in Python the following:
-
A的子集的所有交集:F = {B的交集:B是A的子集}.这是上面的问题，提供了相当不错的解决方案.
All intersections of subsets of A: F = { intersection of B : B is a subset of A }. This was the above question with a decently fast solution.
a. X，Y的所有对(X，Y)都在F中设置，使得X是Y的子集.
a. All pairs (X,Y) for X,Y being sets in F such that X is subset of Y.
b. X，Y的所有对(X，Y)都在F中设置为X是Y的子集，而F中没有集合Z使得Y的Z子集的X子集.换句话说，没有Z适合在X和Y之间按遏制顺序排列.这样的对(X，Y)称为 cover .
b. All pairs (X,Y) for X,Y being sets in F such that X is subset of Y and there is no set Z in F such that X subset of Z subset of Y. In other words, so that no set Z fits in between X and Y in containment order. Such a pair (X,Y) is called cover.
我为什么要这样做? -我想计算10 ^ 7多角形的脸部网格.在这种情况下，上面的集合A包含600套.确实是著名的600个单元格，当前计算大约需要6秒钟，并且如果可能的话，我希望降低10倍.
Why do I want to do that? -- I want to compute face lattices of 10^7 polytopes. In the scenario in mind, the collection A above contains 600 sets. It is indeed the famous 600-cell, the computation currently takes about 6 secs, and I would like that to go down by a factor of 10, if possible.
6秒内获得2.a.只需通过做
The 6 secs to get 2.a. is simply done by doing
# this is John Coleman's function from above question's answer
def allIntersections(frozenSets):
universalSet = frozenset.union(*frozenSets)
intersections = set([universalSet])
for s in frozenSets:
moreIntersections = set(s & t for t in intersections)
intersections.update(moreIntersections)
return intersections
def all_intersections(lists):
sets = allIntersections([frozenset(s) for s in lists])
return [list(s) for s in sets]
A = [[19, 40, 41, 48], [19, 44, 45, 49], [23, 42, 43, 50], [23, 46, 47, 51], [19, 40, 41, 52], [19, 44, 45, 53], [23, 42, 43, 54], [23, 46, 47, 55], [2, 25, 36, 56], [0, 24, 32, 56], [24, 25, 56, 57], [24, 32, 56, 57], [16, 32, 56, 57], [1, 24, 32, 57], [25, 36, 56, 57], [16, 36, 56, 57], [3, 25, 36, 57], [8, 28, 34, 58], [10, 29, 38, 58], [28, 29, 58, 59], [28, 34, 58, 59], [20, 34, 58, 59], [29, 38, 58, 59], [20, 38, 58, 59], [9, 28, 34, 59], [11, 29, 38, 59], [6, 27, 37, 60], [4, 26, 33, 60], [5, 26, 33, 61], [26, 27, 60, 61], [26, 33, 60, 61], [16, 33, 60, 61], [27, 37, 60, 61], [7, 27, 37, 61], [16, 37, 60, 61], [12, 30, 35, 62], [14, 31, 39, 62], [30, 35, 62, 63], [20, 39, 62, 63], [20, 35, 62, 63], [30, 31, 62, 63], [31, 39, 62, 63], [15, 31, 39, 63], [13, 30, 35, 63], [0, 24, 32, 64], [1, 24, 32, 64], [8, 28, 34, 65], [9, 28, 34, 65], [3, 25, 36, 66], [2, 25, 36, 66], [11, 29, 38, 67], [10, 29, 38, 67], [4, 26, 33, 68], [5, 26, 33, 68], [12, 30, 35, 69], [13, 30, 35, 69], [6, 27, 37, 70], [7, 27, 37, 70], [15, 31, 39, 71], [14, 31, 39, 71], [4, 33, 68, 72], [0, 32, 64, 72], [18, 64, 72, 73], [32, 64, 72, 73], [32, 33, 72, 73], [1, 32, 64, 73], [18, 68, 72, 73], [5, 33, 68, 73], [33, 68, 72, 73], [2, 36, 66, 74], [6, 37, 70, 74], [3, 36, 66, 75], [7, 37, 70, 75], [36, 66, 74, 75], [37, 70, 74, 75], [36, 37, 74, 75], [22, 66, 74, 75], [22, 70, 74, 75], [12, 35, 69, 76], [8, 34, 65, 76], [18, 65, 76, 77], [34, 65, 76, 77], [34, 35, 76, 77], [18, 69, 76, 77], [35, 69, 76, 77], [13, 35, 69, 77], [9, 34, 65, 77], [10, 38, 67, 78], [14, 39, 71, 78], [38, 67, 78, 79], [22, 71, 78, 79], [22, 67, 78, 79], [38, 39, 78, 79], [39, 71, 78, 79], [15, 39, 71, 79], [11, 38, 67, 79], [0, 40, 48, 80], [19, 40, 48, 80], [19, 48, 49, 80], [8, 44, 49, 80], [19, 44, 49, 80], [2, 40, 52, 81], [10, 44, 53, 81], [19, 52, 53, 81], [19, 40, 52, 81], [19, 44, 53, 81], [19, 40, 80, 81], [19, 44, 80, 81], [23, 42, 50, 82], [23, 50, 51, 82], [1, 42, 50, 82], [23, 46, 51, 82], [9, 46, 51, 82], [23, 54, 55, 83], [3, 42, 54, 83], [23, 42, 54, 83], [23, 42, 82, 83], [11, 46, 55, 83], [23, 46, 55, 83], [23, 46, 82, 83], [19, 45, 49, 84], [12, 45, 49, 84], [4, 41, 48, 84], [19, 41, 48, 84], [19, 48, 49, 84], [19, 45, 84, 85], [19, 41, 84, 85], [6, 41, 52, 85], [19, 41, 52, 85], [14, 45, 53, 85], [19, 45, 53, 85], [19, 52, 53, 85], [23, 43, 50, 86], [5, 43, 50, 86], [23, 50, 51, 86], [23, 47, 51, 86], [13, 47, 51, 86], [7, 43, 54, 87], [23, 43, 54, 87], [23, 43, 86, 87], [23, 54, 55, 87], [23, 47, 86, 87], [15, 47, 55, 87], [23, 47, 55, 87], [8, 28, 65, 88], [0, 24, 64, 88], [9, 28, 65, 89], [28, 65, 88, 89], [17, 28, 88, 89], [17, 24, 88, 89], [1, 24, 64, 89], [24, 64, 88, 89], [64, 65, 88, 89], [4, 26, 68, 90], [12, 30, 69, 90], [5, 26, 68, 91], [13, 30, 69, 91], [26, 68, 90, 91], [21, 26, 90, 91], [68, 69, 90, 91], [30, 69, 90, 91], [21, 30, 90, 91], [10, 29, 67, 92], [2, 25, 66, 92], [29, 67, 92, 93], [66, 67, 92, 93], [11, 29, 67, 93], [17, 29, 92, 93], [25, 66, 92, 93], [17, 25, 92, 93], [3, 25, 66, 93], [14, 31, 71, 94], [6, 27, 70, 94], [21, 31, 94, 95], [21, 27, 94, 95], [15, 31, 71, 95], [31, 71, 94, 95], [70, 71, 94, 95], [27, 70, 94, 95], [7, 27, 70, 95], [2, 25, 56, 96], [0, 80, 88, 96], [0, 40, 56, 96], [2, 40, 81, 96], [2, 40, 56, 96], [0, 40, 80, 96], [40, 80, 81, 96], [2, 81, 92, 96], [17, 25, 92, 96], [2, 25, 92, 96], [0, 24, 88, 96], [0, 24, 56, 96], [24, 25, 56, 96], [17, 24, 88, 96], [17, 24, 25, 96], [28, 29, 58, 97], [80, 88, 96, 97], [80, 81, 96, 97], [44, 80, 81, 97], [8, 28, 88, 97], [8, 28, 58, 97], [8, 44, 58, 97], [8, 80, 88, 97], [8, 44, 80, 97], [81, 92, 96, 97], [17, 29, 92, 97], [17, 92, 96, 97], [17, 28, 29, 97], [17, 28, 88, 97], [17, 88, 96, 97], [10, 29, 92, 97], [10, 29, 58, 97], [10, 44, 58, 97], [10, 44, 81, 97], [10, 81, 92, 97], [6, 41, 85, 98], [6, 41, 60, 98], [4, 41, 60, 98], [6, 85, 94, 98], [4, 41, 84, 98], [4, 84, 90, 98], [41, 84, 85, 98], [6, 27, 94, 98], [6, 27, 60, 98], [26, 27, 60, 98], [4, 26, 90, 98], [4, 26, 60, 98], [21, 27, 94, 98], [21, 26, 90, 98], [21, 26, 27, 98], [14, 45, 85, 99], [21, 30, 31, 99], [14, 31, 62, 99], [30, 31, 62, 99], [14, 45, 62, 99], [21, 90, 98, 99], [21, 30, 90, 99], [84, 90, 98, 99], [45, 84, 85, 99], [84, 85, 98, 99], [12, 30, 62, 99], [12, 45, 62, 99], [12, 45, 84, 99], [12, 30, 90, 99], [12, 84, 90, 99], [85, 94, 98, 99], [21, 94, 98, 99], [14, 85, 94, 99], [14, 31, 94, 99], [21, 31, 94, 99], [3, 83, 93, 100], [1, 42, 82, 100], [3, 42, 57, 100], [1, 42, 57, 100], [42, 82, 83, 100], [3, 42, 83, 100], [1, 82, 89, 100], [1, 24, 89, 100], [17, 24, 89, 100], [1, 24, 57, 100], [17, 25, 93, 100], [3, 25, 57, 100], [3, 25, 93, 100], [17, 24, 25, 100], [24, 25, 57, 100], [17, 93, 100, 101], [82, 83, 100, 101], [11, 83, 93, 101], [83, 93, 100, 101], [11, 29, 59, 101], [11, 29, 93, 101], [17, 29, 93, 101], [9, 82, 89, 101], [82, 89, 100, 101], [17, 89, 100, 101], [11, 46, 83, 101], [11, 46, 59, 101], [9, 46, 59, 101], [9, 46, 82, 101], [46, 82, 83, 101], [9, 28, 59, 101], [17, 28, 29, 101], [28, 29, 59, 101], [17, 28, 89, 101], [9, 28, 89, 101], [5, 43, 86, 102], [5, 86, 91, 102], [7, 43, 61, 102], [5, 43, 61, 102], [21, 27, 95, 102], [7, 27, 95, 102], [7, 27, 61, 102], [5, 26, 61, 102], [26, 27, 61, 102], [21, 26, 27, 102], [21, 26, 91, 102], [5, 26, 91, 102], [43, 86, 87, 102], [7, 43, 87, 102], [7, 87, 95, 102], [86, 91, 102, 103], [86, 87, 102, 103], [15, 31, 63, 103], [30, 31, 63, 103], [15, 31, 95, 103], [87, 95, 102, 103], [15, 87, 95, 103], [15, 47, 63, 103], [15, 47, 87, 103], [47, 86, 87, 103], [13, 30, 63, 103], [13, 30, 91, 103], [13, 86, 91, 103], [13, 47, 63, 103], [13, 47, 86, 103], [21, 91, 102, 103], [21, 30, 91, 103], [21, 30, 31, 103], [21, 95, 102, 103], [21, 31, 95, 103], [0, 48, 72, 104], [4, 33, 72, 104], [4, 33, 60, 104], [4, 41, 60, 104], [4, 48, 72, 104], [4, 41, 48, 104], [32, 33, 72, 104], [0, 32, 72, 104], [0, 32, 56, 104], [0, 40, 56, 104], [40, 41, 48, 104], [0, 40, 48, 104], [16, 32, 56, 104], [16, 32, 33, 104], [16, 33, 60, 104], [40, 41, 104, 105], [40, 41, 52, 105], [41, 60, 104, 105], [16, 60, 104, 105], [40, 56, 104, 105], [16, 56, 104, 105], [2, 40, 56, 105], [2, 40, 52, 105], [2, 36, 56, 105], [16, 36, 56, 105], [16, 37, 60, 105], [16, 36, 37, 105], [2, 52, 74, 105], [36, 37, 74, 105], [2, 36, 74, 105], [6, 52, 74, 105], [6, 41, 52, 105], [6, 41, 60, 105], [6, 37, 60, 105], [6, 37, 74, 105], [12, 35, 76, 106], [12, 45, 62, 106], [12, 35, 62, 106], [8, 44, 49, 106], [8, 49, 76, 106], [12, 49, 76, 106], [44, 45, 49, 106], [12, 45, 49, 106], [20, 35, 62, 106], [8, 44, 58, 106], [20, 34, 58, 106], [8, 34, 58, 106], [20, 34, 35, 106], [8, 34, 76, 106], [34, 35, 76, 106], [20, 62, 106, 107], [20, 38, 39, 107], [20, 39, 62, 107], [10, 38, 78, 107], [38, 39, 78, 107], [10, 53, 78, 107], [20, 58, 106, 107], [20, 38, 58, 107], [10, 38, 58, 107], [44, 58, 106, 107], [10, 44, 58, 107], [10, 44, 53, 107], [14, 39, 62, 107], [14, 39, 78, 107], [14, 53, 78, 107], [14, 45, 53, 107], [44, 45, 106, 107], [44, 45, 53, 107], [14, 45, 62, 107], [45, 62, 106, 107], [16, 32, 57, 108], [1, 32, 57, 108], [16, 32, 33, 108], [16, 33, 61, 108], [5, 33, 61, 108], [1, 32, 73, 108], [32, 33, 73, 108], [1, 50, 73, 108], [5, 33, 73, 108], [5, 50, 73, 108], [1, 42, 50, 108], [1, 42, 57, 108], [5, 43, 61, 108], [5, 43, 50, 108], [42, 43, 50, 108], [7, 37, 61, 109], [3, 36, 57, 109], [3, 42, 57, 109], [7, 43, 61, 109], [42, 43, 108, 109], [43, 61, 108, 109], [42, 57, 108, 109], [16, 36, 57, 109], [16, 36, 37, 109], [16, 57, 108, 109], [16, 61, 108, 109], [16, 37, 61, 109], [36, 37, 75, 109], [7, 37, 75, 109], [3, 36, 75, 109], [3, 42, 54, 109], [42, 43, 54, 109], [7, 43, 54, 109], [3, 54, 75, 109], [7, 54, 75, 109], [34, 35, 77, 110], [13, 35, 63, 110], [13, 35, 77, 110], [13, 47, 63, 110], [9, 34, 77, 110], [9, 51, 77, 110], [13, 51, 77, 110], [9, 46, 51, 110], [13, 47, 51, 110], [46, 47, 51, 110], [20, 35, 63, 110], [20, 34, 35, 110], [9, 34, 59, 110], [20, 34, 59, 110], [9, 46, 59, 110], [11, 38, 59, 111], [11, 38, 79, 111], [15, 47, 63, 111], [11, 55, 79, 111], [15, 47, 55, 111], [15, 55, 79, 111], [11, 46, 59, 111], [46, 47, 55, 111], [11, 46, 55, 111], [38, 39, 79, 111], [15, 39, 79, 111], [15, 39, 63, 111], [20, 38, 39, 111], [20, 39, 63, 111], [20, 38, 59, 111], [47, 63, 110, 111], [20, 59, 110, 111], [20, 63, 110, 111], [46, 59, 110, 111], [46, 47, 110, 111], [8, 65, 88, 112], [18, 65, 76, 112], [8, 65, 76, 112], [8, 49, 76, 112], [0, 64, 88, 112], [64, 65, 88, 112], [18, 64, 65, 112], [18, 64, 72, 112], [0, 64, 72, 112], [0, 48, 72, 112], [8, 49, 80, 112], [8, 80, 88, 112], [48, 49, 80, 112], [0, 48, 80, 112], [0, 80, 88, 112], [4, 68, 90, 113], [4, 84, 90, 113], [12, 84, 90, 113], [18, 68, 69, 113], [68, 69, 90, 113], [12, 69, 90, 113], [4, 68, 72, 113], [18, 68, 72, 113], [18, 69, 76, 113], [12, 69, 76, 113], [4, 48, 84, 113], [4, 48, 72, 113], [12, 49, 76, 113], [48, 49, 84, 113], [12, 49, 84, 113], [18, 76, 112, 113], [49, 76, 112, 113], [18, 72, 112, 113], [48, 49, 112, 113], [48, 72, 112, 113], [2, 66, 92, 114], [66, 67, 92, 114], [52, 53, 81, 114], [2, 52, 81, 114], [2, 81, 92, 114], [22, 66, 67, 114], [22, 67, 78, 114], [2, 66, 74, 114], [2, 52, 74, 114], [22, 66, 74, 114], [10, 53, 81, 114], [10, 53, 78, 114], [10, 67, 78, 114], [10, 81, 92, 114], [10, 67, 92, 114], [6, 85, 94, 115], [6, 52, 85, 115], [52, 53, 85, 115], [14, 85, 94, 115], [14, 53, 85, 115], [52, 53, 114, 115], [6, 52, 74, 115], [52, 74, 114, 115], [14, 71, 94, 115], [70, 71, 94, 115], [6, 70, 94, 115], [6, 70, 74, 115], [22, 74, 114, 115], [22, 70, 74, 115], [22, 70, 71, 115], [14, 71, 78, 115], [53, 78, 114, 115], [14, 53, 78, 115], [22, 78, 114, 115], [22, 71, 78, 115], [18, 64, 65, 116], [18, 65, 77, 116], [50, 51, 82, 116], [1, 50, 82, 116], [9, 51, 82, 116], [9, 51, 77, 116], [9, 65, 77, 116], [18, 64, 73, 116], [1, 64, 73, 116], [1, 50, 73, 116], [64, 65, 89, 116], [1, 64, 89, 116], [9, 65, 89, 116], [1, 82, 89, 116], [9, 82, 89, 116], [18, 73, 116, 117], [18, 77, 116, 117], [51, 77, 116, 117], [18, 69, 77, 117], [13, 51, 86, 117], [13, 51, 77, 117], [13, 69, 77, 117], [18, 68, 69, 117], [18, 68, 73, 117], [13, 69, 91, 117], [13, 86, 91, 117], [68, 69, 91, 117], [5, 86, 91, 117], [5, 68, 73, 117], [5, 68, 91, 117], [50, 51, 116, 117], [5, 50, 86, 117], [50, 51, 86, 117], [5, 50, 73, 117], [50, 73, 116, 117], [11, 55, 83, 118], [3, 66, 75, 118], [3, 54, 75, 118], [3, 54, 83, 118], [54, 55, 83, 118], [11, 55, 79, 118], [11, 67, 79, 118], [66, 67, 93, 118], [3, 83, 93, 118], [3, 66, 93, 118], [11, 67, 93, 118], [11, 83, 93, 118], [22, 66, 67, 118], [22, 67, 79, 118], [22, 66, 75, 118], [54, 55, 87, 119], [54, 55, 118, 119], [55, 79, 118, 119], [54, 75, 118, 119], [22, 75, 118, 119], [22, 79, 118, 119], [22, 71, 79, 119], [22, 70, 71, 119], [70, 71, 95, 119], [22, 70, 75, 119], [7, 54, 75, 119], [7, 54, 87, 119], [7, 70, 75, 119], [7, 87, 95, 119], [7, 70, 95, 119], [15, 71, 79, 119], [15, 55, 79, 119], [15, 55, 87, 119], [15, 71, 95, 119], [15, 87, 95, 119]]
from itertools import combinations
F = all_intersections(A) # all intersections: function from other question
# takes 415 ms
F = sorted(F,lambda x,y: cmp(len(x),len(y)))
pairs = [ (x,y) for x,y in combinations(F,2) if set(y).issuperset(x) ]
# takes ~6 sec
一个例子是正方形，其顶点标记为{1,2,3,4}:则集合A为{{1,2}，{2,3}，{3,4}，{4,1 }}，交点F为{{}，{1}，{2}，{3}，{4}，{1,2}，{2,3}，{3,4}，[4,1} ，{1,2,3,4}}和有问题的对是
An example is the square with vertices labelled with {1,2,3,4}: the set A is then {{1,2},{2,3},{3,4},{4,1}}, the intersections F are {{},{1},{2},{3},{4},{1,2},{2,3},{3,4},[4,1},{1,2,3,4}}, and the pairs in question are
({},{1}),({},{2}),({},{3}),({},{4}),
({1},{1,2}),({1},{4,1}),
({2},{1,2}),({2},{2,3}),
({3},{2,3}),({3},{3,4}),
({4},{3,4}),({4},{4,1}),
({1,2},{1,2,3,4}),({2,3},{1,2,3,4}),({3,4},{1,2,3,4}),({4,1},{1,2,3,4})
一旦给定了集合F，我认为没有什么比仅比较元素更好的了.但是我更多地考虑的是一种算法，该算法利用与刚刚相交的东西有关的知识同时计算(1)和(2).
Once you are given the set F, I don't think there is anything better than just comparing the elements. But I am more thinking of an algorithm that computes (1) and (2) at the same time using the knowledge about stuff that was just intersected.
在下面的David K解决方案之后，给出为什么，还有两个可以使用的假设:
Following the solution by David K below, given the why, there are two more assumptions that can be used:
-
使用唯一的最小和唯一的最大元素对结果订单进行评级.即，每个最大链F 0 ＜0. F1 ＜ ...<覆盖关系的Fm具有相同的长度，F0是空集，Fm是输入集A的并集.我们称集Fi的等级为i，这在给定等级的情况下是明确定义的.
The resulting order is graded with a unique minimal and a unique maximal element. This is, every maximal chain F0 < F1 < ... < Fm of cover relations has the same length and F0 is the empty set and Fm is the union of the input sets A. We call the set Fi to be of rank i, which is well-defined given the graded-ness.
每个等级M集都是2个等级M + 1集的交集.
Every rank M set is the intersection of exactly 2 rank M+1 sets.
非常感谢！
推荐答案
这里的函数利用了以下假设:输入中的列表是抽象多面体的方面.与其采取所有不同的构面集合， 此函数假定输入是在M + 1的多面体中的M面(M的多面体)的完整列表. 然后，它执行一个循环，在该循环中，每次迭代都获取完整的M张面孔列表，并生成完整的(M-1)张面孔列表，同时累积这两个面孔列表的所有包含对.
Here's a function that takes advantage of the assumption that the lists in the input are the facets of an abstract polytope. Instead of taking all intersections of collections of facets, this function assumes the input is a complete list of M-faces (polytopes of rank M) within a polytope of rank M + 1. It then performs a loop in which each iteration takes a complete list of M-faces and produces a complete list of (M-1)-faces, while accumulating all the containment pairs for those two lists of faces.
该函数的主循环与每对M面相交，并构建一个结构，列出每个交点以及包含该交点的M面. 这些交集包括所有(M-1)张脸，但也包括 一些低等的面孔.可以识别较低等级的面孔 通过观察它们中的每一个都是(M-1)张脸的子集， 这样就消除了作为另一个交集的子集的任何交集.
The main loop of the function intersects each pair of M-faces and builds a structure listing each intersection and the M-faces that contained it. These intersections include all the (M-1)-faces, but also include some lower-rank faces. The lower-rank faces can be identified by observing that each of them is a subset of an (M-1)-face, so any intersection which is a subset of another intersection is eliminated.
运行时间的粗略分类为40％，以使两副面孔相交， 40％跟踪哪些M面包含每个结果 交集，消除10％小于M-1的面孔 10％的用户将包含对写入输出列表. 我的电脑似乎比你的电脑慢 (约8秒，而不是原始功能的6或6.5秒)， 但是新功能的最终结果是所有包含项的列表 每个等级和下一个等级之间的配对，比 产生所有包含对(包括 那些跳过"排名的人.
A rough breakdown of the running time is 40% to intersect pairs of faces, 40% to keep track of which M-faces contained each of the resulting intersections, 10% to eliminate faces of rank less than M - 1, and 10% to write the containment pairs to the output list. My computer seems to be slower than yours (about 8 seconds instead of 6 or 6.5 seconds for the original function), but the end result of the new function is a list of all the containment pairs between each rank and the next rank, about 10x-15x faster than the original function that produces all containment pairs (including the ones that "skip" ranks).
请注意，并非整数列表中的每个列表都是新输入的有效输入 函数，因为有一些点集的集合 抽象多面体的多个方面.我没有包含用于检查输入的代码 为了正确.
Note that not every list of lists of integers is valid input for the new function, because there are collections of sets of points that are not facets of an abstract polytope. I did not include code to check the input for correctness.
要检查输出的正确性，我在原始函数中添加了一些(相当慢的)代码以在(原始)输出列表中找到所有对(s，t)
这样列表中的(s，u)和(u，t)形式的对也都在列表中，
然后返回删除所有那些对的修订列表.
我还通过调用sorted()修改了新功能和旧功能
他们在输出中放入的每个整数列表，以便输出列表
会正确比较.
然后，我确认这两个函数产生了相同的输出.
To check correctness of the output, I added some (rather slow) code to the original function to find all pairs (s,t) in the (original) output list
such that pairs of the form (s,u) and (u,t) were also in the list,
and then return a revised list with all those pairs removed.
I also modified both the new and old functions by invoking sorted() on
each list of integers they put in the output so that the output lists
would compare correctly.
I then confirmed that both functions produced identical output.
顺便说一句，我怀疑这个函数是否像以前那样是pythonic的. 欢迎提出建议在此问题上进行改进的评论.
By the way, I doubt this function is a pythonic as it could have been. Comments suggesting improvements in that matter are welcome.
from collections import defaultdict
import sys
def generatePairs(A):
# It is assumed that A consists exactly of all the facets of an abstract
# polytope of rank N; that is, the abstract polytope is a graded poset
# in which the minimal element is the empty set and has rank -1, the
# maximal element is the polytope's body, which has rank N, and A
# contains all facets of the polytope, which have rank N - 1.
# Then within the graded poset,
# each element of rank 0 is a point and has cardinality 1;
# each element of rank 1 is an edge and has cardiality 2;
# each element of rank M (where M > 1) is a rank-M polytope and has
# cardinality at least M + 1, but may have greater cardinality.
# We start with the facets (rank N-1).
rank_to_intersect = [frozenset(s) for s in A]
# Construct the body (rank N).
polytope_body = list(frozenset.union(*rank_to_intersect))
body_size = len(polytope_body)
# covering_pairs will be all the pairs of polytopes (s,t) such that
# rank(s) + 1 == rank(t) and s is a subset of t. Initially we populate
# it with just the pairs whose ranks are respectively N-1 and N.
covering_pairs = [(s, polytope_body) for s in A]
while (len(rank_to_intersect) > 0) and (len(rank_to_intersect[0]) > 2):
# For some integer M such that M > 1, rank_to_intersect contains all
# the polytopes of rank M. At the end of each iteration of the loop,
# rank_to_intersect will contain all the polytopes of rank M - 1.
# Also, all the pairs (x,y) where rank(x) = M - 1 and rank(y) = M
# will have been added to covering_pairs.
container_map = defaultdict(list)
while rank_to_intersect:
s = rank_to_intersect.pop()
for t in rank_to_intersect:
x = s & t
if len(x) > 1:
container_map[x].extend([s, t])
# Note that the list container_map[x]
# may contain duplicates
# The keys of container_map, consisting of all pairwise
# intersections of polytopes of rank M, include all polytopes
# of rank M - 1 but also some polytopes of lower ranks.
# Any polytope of a lower rank, however, is a subset of
# a polytope of rank M - 1 that is also in the list.
min_size = min([len(s) for s in container_map.keys()])
max_size = max([len(s) for s in container_map.keys()])
size_range = range(min_size, max_size + 1)
candidates = dict([(i, []) for i in size_range])
for s in container_map.keys():
candidates[len(s)].append(s)
# Repopulate rank_to_intersect with the polytopes of rank M - 1.
for set_size in size_range:
larger_sizes = range(set_size + 1, max_size + 1)
for s in candidates[set_size]:
if not any(any(t >= s for t in candidates[i])
for i in larger_sizes):
# We now know that s has rank M - 1, not a lower rank.
rank_to_intersect.append(s)
# Add all the (rank-(M - 1), rank-M) pairs to covering_pairs.
for s in rank_to_intersect:
# container_map[s] may contain duplicates; avoid them.
containers = frozenset(container_map[s])
covering_pairs.extend([(list(s), list(t)) for t in containers])
# At the end of the loop, rank_to_intersect contains the rank-1
# polytopes, that is, the edges.
# Each edge contains each of its two endpoints.
points_with_duplicates = []
for e in rank_to_intersect:
covering_pairs.extend([([p], list(e)) for p in e])
points_with_duplicates.extend(e)
# List the containment pairs of the empty set without duplicating points.
points = frozenset(points_with_duplicates)
covering_pairs.extend([([], [p]) for p in points])
return covering_pairs
这篇关于如何快速计算集合集合所有交点的包含顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
