代码之家 › 专栏 › 技术社区 › ShanZhengYang

在python字典中计算数字的“唯一对”?

nested-lists itertools dictionary python-3.x python

-1

ShanZhengYang · 技术社区 · 6 年前

编辑:编辑的打字错误;字典的键值应该是字典,而不是集合。

尽管如此,我还是会在这里保留打字错误,因为下面的问题解决了这个问题。很抱歉给你添麻烦。

假设我有一个从不重复的整数列表:

list1 = [2, 3]

在这种情况下,有一个唯一的对2-3和3-2,所以字典应该是:

{2:{3: 1}, 3:{2: 1}}

也就是说,有1对2-3和1对3-2。

对于较大的列表,配对是相同的,例如。

list2 = [2, 3, 4]

{2:{3: 1}, 3:{2: 1}, 3:{4: 1}, 4:{3: 1}, 2:{4: 1}, 4:{2: 1}}

(2) 我提到列表不能有重复的整数,例如。

[2, 2, 3]

是不可能的,因为有两个2。

但是,可以有一个列表:

list3 = [[2, 3], [2, 3, 4]]

{2:{3: 2}, 3:{2: 2}, 3:{4: 1}, 4:{3: 1}, 2:{4: 1}, 4:{2: 1}}

因为有两对2-3和3-2。如果一个列表中有多个列表,如何“更新”词典?

这是一个算法问题,我不知道最有效的解决办法。我的想法是以某种方式缓存列表中的值并枚举对…但那太慢了。我猜这里面有些有用的东西 itertools .

2 回复 | 直到 6 年前

Olivier Melançon iacob 6 年前

你要做的是计算由列表中的组合产生的对。你可以找到那些 Counter 和 combinations

from itertools import combinations
from collections import Counter

list2 = [2, 3, 4]

count = Counter(combinations(list2, 2))

print(count)

输出

Counter({(2, 3): 1, (2, 4): 1, (3, 4): 1})

计数器 每个子列表的结果。

from itertools import combinations
from collections import Counter

list3 = [[2, 3], [2, 3, 4]]

count = Counter()

for sublist in list3:
    count.update(Counter(combinations(sublist, 2)))

print(count)

输出

Counter({(2, 3): 2, (2, 4): 1, (3, 4): 1})

semore_1267 6 年前

我的方法迭代输入 dict (线性复杂度)并将每个键与其第一个可用整数配对(此复杂度取决于问题的确切规格-例如,每个列表是否可以包含无限的子列表?),将它们插入到输出dict(常量复杂性)中。

import os 
import sys 


def update_results(result_map, tup):
    # Update dict inplace
    # Don't need to keep count here
    try:
        result_map[tup] += 1
    except KeyError:
        result_map[tup] = 1
    return


def algo(input):
    # Use dict to keep count of unique pairs while iterating
    # over each (key, v[i]) pair where v[i] is an integer in 
    # list input[key]
    result_map = dict()
    for key, val in input.items():
        key_pairs = list()
        if isinstance(val, list):
            for x in val:
                if isinstance(x, list):
                    for y in x:
                        update_results(result_map, (key, y))
                else:
                    update_results(result_map, (key, x))
        else:
            update_results(result_map, (key, val))
    return len(result_map.keys())


>>> input = { 1: [1, 2], 2: [1, 2, [2, 3]] }
>>> algo(input)
>>> 5