<p>所以,我想不出一个聪明的解决方案,不需要将每个值集与其他值集进行比较。我不指望这是非常性能,但它可能足够了。首先,让我们从我们的字典开始:</p>
<pre><code>In [12]: d
Out[12]:
{'key1': ['1', '3', '4', '7'],
'key2': ['7', '3', '2', '1'],
'key3': ['5', '2', '3', '1'],
'key4': ['4', '5', '1', '3']}
</code></pre>
<p>现在,我们将把列表改为<code>frozensets</code></p>
<pre><code>In [14]: ds = {k:frozenset(v) for k,v in d.items()}
In [16]: ds
Out[16]:
{'key1': frozenset({'1', '3', '4', '7'}),
'key2': frozenset({'1', '2', '3', '7'}),
'key3': frozenset({'1', '2', '3', '5'}),
'key4': frozenset({'1', '3', '4', '5'})}
</code></pre>
<p>这允许我们获得交叉点,并且可以散列:</p>
<pre><code>In [17]: ds['key1'] & ds['key2']
Out[17]: frozenset({'1', '3', '7'})
In [18]: inverse = {}
</code></pre>
<p>所以,现在我们创建一个中间层。这将花费最长的处理时间:</p>
<pre><code>In [20]: import itertools
In [21]: for k1, k2 in itertools.combinations(ds, 2):
...: inverse.setdefault(ds[k1] & ds[k2], []).extend((k1, k2))
...:
In [22]: inverse
Out[22]:
{frozenset({'1', '3'}): ['key1', 'key3', 'key2', 'key4'],
frozenset({'1', '2', '3'}): ['key2', 'key3'],
frozenset({'1', '3', '7'}): ['key1', 'key2'],
frozenset({'1', '3', '5'}): ['key3', 'key4'],
frozenset({'1', '3', '4'}): ['key1', 'key4']}
</code></pre>
<p>现在我们有了你想要的数据,但是现在有了你想要的密钥方案。为此,我们可以采取如下措施:</p>
<pre><code>In [23]: from collections import defaultdict
In [24]: lenmap = defaultdict(lambda: itertools.count(1))
</code></pre>
<p>最后:</p>
<pre><code>In [25]: inverse2 = {}
...: for k, v in inverse.items():
...: inverse2["group{}.{}".format(len(k), next(lenmap[len(k)]))] = v
...:
In [26]: inverse2
Out[26]:
{'group2.1': ['key1', 'key3', 'key2', 'key4'],
'group3.1': ['key2', 'key3'],
'group3.2': ['key1', 'key2'],
'group3.3': ['key3', 'key4'],
'group3.4': ['key1', 'key4']}
</code></pre>
<p>不幸的是,创建<code>inverse</code>的步骤将是多项式时间。它至少是O(n^2),其中n是字典的大小,但实际上,我认为它是O(n^2*m),其中m是键之间成对最小长度的最大值。可能不太可怕。<strong>编辑</strong>刚刚注意到在一条评论中,每个值都是10个URL的列表。在这种情况下,第二个中间步骤仅仅是O(n^2),因为m是常数。你知道吗</p>