Считать «уникальные пары» чисел в словарь Python? - PullRequest
Новая
       23

Считать «уникальные пары» чисел в словарь Python?

0 голосов
/ 06 сентября 2018

РЕДАКТИРОВАТЬ: отредактированные опечатки; ключевые значения словаря должны быть словарями, а не наборами.

Я оставлю здесь опечатки, так как приведенные ниже вопросы касаются этого вопроса. Мои извинения за путаницу.

Вот проблема:

Допустим, у меня есть список целых чисел, которые никогда не повторяются: 

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?

(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 ]

0 голосов
/ 06 сентября 2018

Мой подход перебирает ввод 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

Я почти уверен, что есть более изощренный способ сделать это (опять же, это будет зависеть от точных спецификаций вашего вопроса), но это может помочь вам начать (без импорта)

0 голосов
/ 06 сентября 2018

То, что вы хотите, это подсчитать пары, которые возникают из комбинаций в ваших списках. Вы можете найти те с 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})
...