将 "unique pairs" 个数字计入 python 字典？

Question

编辑：编辑错别字；字典的键值应该是字典，而不是集合。

我会保留这里的错别字，因为下面的问题解决了这个问题。对于造成的混乱，我深表歉意。

这是问题所在：

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

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}}

(1) 一旦列表的大小变得更大，如何使用 python 数据结构通过算法找到这种格式的 "unique pairs"？

(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。一个 "update" 字典如何在一个列表中给出多个列表？

这是一个算法问题，我不知道最有效的解决方案。我的想法是以某种方式在列表中缓存值并枚举对......但那会很慢。我猜 itertools.

有一些有用的东西

Answer 1

你想要的是计算列表中组合产生的对。您可以找到带有 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})

关于您的列表列表，我们用每个子列表的结果更新 Counter。

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})

Answer 2

我的方法遍历输入 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

我很确定有一种更完善的方法可以做到这一点（同样，这取决于您问题的具体规格），但这可以让您入门（无导入）

将 "unique pairs" 个数字计入 python 字典？

Counting "unique pairs" of numbers into a python dictionary?

python

dictionary

nested-lists

itertools

python-3.x

输出

输出