2

我有一本字典。如果 V 在 DICT[K] 中，则 someFunc(k, v) 和 someFunc(v, k) 都返回 true（并且 K 在 DICT[V] 中）。字典可能如下所示：

{
1: [2, 3, 5],
2: [3, 1, 5],
3: [1, 2],
5: [2, 1],
}

我想在符合此标准的字典中找到具有一定长度的所有数字集：对于字典中的任何对， someFunc(x, y) 和 someFunc(y, x) 必须为真。例如，对于我展示的字典：

{1, 2, 3} 将是一个有效的长度为 3 的集合。条件必须有效，因为所有项目都包含其他项目：

  • dict[1] 包含 2, 3
  • dict[2] 包含 1, 3
  • dict[3] 包含 1, 2

如果我知道所有有效集合必须包含给定数字，那么在给定字典中找到所有这些给定长度的集合的最佳方法是什么。

4

1 回答 1

1 
from itertools import combinations
from collections import OrderedDict

def sf(k,v,d):
    return (k in d[v]) and (v in d[k])

def lenN(d, n):
    # create a list of unique items
    l = list(OrderedDict.fromkeys(i for x in d for i in d[x]))
    # collect matching groups
    V = list()
    for C in combinations(l, n):
        for P in combinations(C, 2):
            if not sf(P[0], P[1], d): break
        else: V.append(C)
    return V

d = { 1: [2, 3, 5], 2: [3, 1, 5], 3: [1, 2], 5: [2, 1], }

print lenN(d, 3)

输出

[(2, 3, 1), (2, 5, 1)]
于 2013-05-24T04:56:45.383 回答