Блог

У меня есть упорядоченный словарь, содержащий нециклические ссылки на другие элементы в словаре:

 from collections import OrderedDict
ug = OrderedDict(a=[],b=['e'],c=['a','b'],d=['a'],e=[])
  

Теперь я хотел бы

1. упорядочите словарь так, чтобы ссылки указывали только назад на ключи перед каждым ключом, и,
2. минимизируйте «ссылочное расстояние» в упорядоченном словаре.

Ниже показано, как может выглядеть такая функция расстояния:

 def distance(g):
    total_distance = 0
    ordered = True
    for i,i_key in enumerate(list(g)):
        for j_index,j_key in enumerate(g[i_key]):
            j = list(g).index(j_key)
            print(str(j_key)   ' -> '   str(i_key)   ' = '   str(i)   ' - '   str(j)   ' = '   str(i-j))
            total_distance  = i - j
            if (i < j):
                ordered = False
    
    if ordered:
        print('total_distance: '   str(total_distance)   'n')
        return (total_distance)
    else:
        print('not in ordern')
        return None
  

Вот исходный список для тестирования:

 ug = OrderedDict(a=[],b=['e'],c=['a','b'],d=['a'],e=[])
distance(ug)
  

предоставление

 e -> b = 1 - 4 = -3
a -> c = 2 - 0 = 2
b -> c = 2 - 1 = 1
a -> d = 3 - 0 = 3
not in order
  

И вот два новых порядка, имеющих только обратные ссылки:

 og1 = OrderedDict(e=[],a=[],d=['a'],b=['e'],c=['a','b'])
distance(og1)

og2 = OrderedDict(a=[],d=['a'],e=[],b=['e'],c=['a','b'])
distance(og2)
  

что приведет к

 a -> d = 2 - 1 = 1
e -> b = 3 - 0 = 3
a -> c = 4 - 1 = 3
b -> c = 4 - 3 = 1
total_distance: 8

a -> d = 1 - 0 = 1
e -> b = 3 - 2 = 1
a -> c = 4 - 0 = 4
b -> c = 4 - 3 = 1
total_distance: 7
  

Как минимизировать такое общее расстояние при упорядочении такого словаря, который содержит только обратные ссылки на ключи? Нет необходимости придерживаться OrderedDict структуры данных. Также ключи 'a','b',...,'e' могут быть просто представлены в виде чисел, если какая-то другая структура данных окажется более краткой.

Одним из дополнительных решений может быть:

• создайте все возможные перестановки данного OrderDict ,

• map каждый элемент с функцией, которую вы предоставляете для измерения расстояний,

• фильтровать все None s, что означает, что они не соответствуют условию обратной ссылки,

• наконец, выберите перестановку, которая приведет к минимальному расстоянию

реализация:

 def distance(g):
    total_distance = 0
    ordered = True
    for i,i_key in enumerate(list(g)):
        for j_index,j_key in enumerate(g[i_key]):
            # print(j_key)
            j = list(g).index(j_key)
            # print(str(j_key)   ' -> '   str(i_key)   ' = '   str(i)   ' - '   str(j)   ' = '   str(i-j))
            total_distance  = i - j
            if (i < j):
                ordered = False
    
    if ordered:
        # print('total_distance: '   str(total_distance)   'n')
        return total_distance
    else:
        # print('not in ordern')
        return None

from collections import OrderedDict
import itertools
ug = OrderedDict(a=[],b=['e'],c=['a','b'],d=['a'],e=[])

all_permutations = list(itertools.permutations(ug.items()))
all_permutations = [OrderedDict(item) for item in all_permutations]
mapped = map(distance, all_permutations)
mapped = [(item,iter) for iter,item in enumerate(mapped) if item is not None]
minimal_permutation = min(list(mapped))
print("minimal distance is: "   str(minimal_permutation[0]))
print(all_permutations[minimal_permutation[1]])
  

вывод:

 minimal distance is: 6
OrderedDict([('e', []), ('b', ['e']), ('a', []), ('c', ['a', 'b']), ('d', ['a'])])
  

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