Как перейти из пары ключ-значение в словаре, чтобы создать список цикла - PullRequest
Новая
       33

Как перейти из пары ключ-значение в словаре, чтобы создать список цикла

0 голосов
/ 29 сентября 2019

В моей домашней работе цикл определяется как набор ключей, которые переходят от ключа -> значение -> ключ, который возвращается к своему первоначальному начальному значению.Например: 

d1 = {1:6, 3:1, 6:3}
cycles = [[1, 6, 3]]

потому что 1: 6 -> 6: 3 -> 3: 1, а стартовый ключ == последнее значение

Аналогично для следующего словаря: 

d1 = {1: 5, 2: 14, 3: 15, 4: 3, 5: 5, 6: 5, 
      7: 15, 8: 6, 9: 10, 10: 15, 11: 12, 
      12: 15, 13: 14, 14: 8, 15: 9}

Правильно упорядоченные циклы, заданные отображением: [[5], [9, 10, 15]] (также потому, что 5: 5 - полный цикл, а 9:10 -> 10:15 -> 15: 9) Есть ли способсоздать цикл для отслеживания этих циклов в словарях?Я хочу создать строку, которая будет работать для любых случайных сопоставлений словаря значения ключа. 

cycle=[]
For k,v in d1.items():
    if k == v:
        cycle.append([k])

For k,v in mapping2.items
    if k!=v:
        if v in keys:
            start_k = k

If mapping[k] in keys:

Ответы [ 2 ]

0 голосов
/ 29 сентября 2019

Это должно работать. 

#!/usr/bin/env python3

def get_cycles(d):
    cycles = []

    while d:
        # Keep track of keys we've iterated through in this loop
        tracked = []

        # Take the next available key
        k = next(iter(d))

        while True:
            tracked.append(k)

            # This key (the value of the previous key) must have already 
            # been deleted, meaning it was part of a cycle or lead to 
            # repetitions of an already discovered cycle
            try:
                v = d[k]
            except KeyError:
                # Always delete keys leading up to the current key too, as this
                # same loop will happen every time we land on one of these keys
                # otherwise
                for t in tracked:
                    if t in d:
                        del d[t]
                break

            # If the value of the current key was one of the keys leading up to
            # the current key, we've discovered a cycle starting from the value
            # of the current key and ending at the current key
            if v in tracked:
                cycle = tracked[tracked.index(v):]
                cycles.append(cycle)
                for c in cycle:
                    del d[c]
                break

            # If the value of the current key is a key in any of the
            # previously discovered cycles, we want to delete this sequence,
            # as we've already discovered the cycle it leads to
            if any(v in cycle for cycle in cycles):
                for t in tracked:
                    del d[t]
                break

            # Set the next key
            k = v

    return cycles


d1 = {1: 5, 2: 14, 3: 15, 4: 3, 5: 5, 6: 5, 7: 15, 8: 6, 9: 10, 10: 15, 11: 12, 12: 15, 13: 14, 14: 8, 15: 9}
d2 = {1:6, 3:1, 6:3}

print(get_cycles(d1))
print(get_cycles(d2))

Вывод: 

[[5], [15, 9, 10]]
[[1, 6, 3]]

Алгоритм отслеживает каждый ключ, через который он проходит, повторяясь, устанавливая ключ, равный его собственному значению.

Если значение ключа уже находится в списке повторяющихся ключей, цикл обнаружен от этой позиции в списке повторяющихся ключей до конца.Отслеживаемые ключи, которые приводят к обнаружению этого цикла, должны быть затем удалены из словаря, так как этот цикл уже пройден.

Если значение ключа является ключом в одном из ранее обнаруженных циклов, тотекущая последовательность пройденных ключей должна быть удалена из словаря, так как цикл, к которому ведет эта последовательность, уже обнаружен.

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

0 голосов
/ 29 сентября 2019

Этот ответ объясняет один потенциальный алгоритм, но не реализует его.Если вы хотите найти алгоритм самостоятельно, прекратите чтение.

Возможно, есть более разумные способы, но один из них будет.Если у вас есть dict с n ключами, то вам понадобится n итераций для обнаружения всех потенциальных циклов.

Давайте назовем начальный dict d и предположим, что он имеет N (прописные N) пар ключ / значение

1.) Сделать копию d cpy = dict (d)

Начальная итерация для длины цикла n = 1: найти все ключи в cpy, где cpy [key] == key

добавить их в список решений и удалить эти записи из скопированного dict

Первая итерация для длины цикла n = 2: создать новый dict cpy2 следующим образом: для каждого ключа cp создать val, то есть вычисляется d[cp[key]], теперь присваиваем cpy2 cpy cpy = cpy2

, теперь ищем все ключи в cpy, где cpy [key] == key вы знаете, что для этих значений у вас есть циклы длины n иесли вы хотите, вы можете восстановить их, начиная с ввода в d и повторяя n раз

Вторая итерация для длины цикла n = 3: следуйте инструкциям из первой итерации.

Итерация до длины цикла n == N

При таком подходе вы сможете идентифицировать все циклы.Однако если бы у вас был цикл длины n, у вас было бы n решений для одного и того же цикла.

Например, если у вас был цикл [9, 10, 15], то вы найдете: [10, 15, 9], а также[15, 10, 9] Таким образом, вы, вероятно, должны исключить или даже не хранить какое-либо решение, если первое значение в цикле не является наименьшим значением в списке значений

...