CODEWITHSUNDEEP
pythondistancedirected-graphordereddictionary
Heikki
Heikki

Reputation: 2254

How to minimize distances in ordered dictionary containing only backward references to the keys?

I have an ordered dictionary containing non-cyclical references to other elements in the dictionary:

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

Now I would like to

  1. order the dictionary so that the references would point only backwards to the keys before the each key, and,
  2. minimize the 'reference distance' in the ordered dictionary.

Below is shown how such distance function could look like:

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 order\n')
        return None

Here is the original list for testing:

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

giving

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

And here are two new orders having only backward references:

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)

which will produce

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

How to minimize such total distance in ordering such dictionary which contains only backward references to the keys? There is no need to stick to OrderedDict data structure. Also keys 'a','b',...,'e' could simply be represented as numbers, if some other data structure would prove out to be more concise.

Upvotes: 2

Views: 32

Answers (1)

Yossi Levi
Yossi Levi

Reputation: 1268

One optional solution can be:

  • create all possible permutations of the given OrderDict,

  • map each element with the function you provide to measure the distances,

  • filter all the Nones which means that they do not meet the condition of backward reference,

  • finally pick up the permutation that bring up the minimal distance

implementation:

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 order\n')
        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]])

output:

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

Notice that this solution is risky as the number of permutations can extremely diverge as factor of len(ug), but in the other hand I can't find out another approach to find the best permutations without walking through each one of them at least once.

Upvotes: 1

Related Questions