Dictionary sorting by order in Python

Question

I am trying to create a script that will take a dictionary of unique keys, and sort by their similar listed string values. Each value is listed in order of preference from an imported csv. I am new to python and am having some trouble in conceptualizing this, but so far I have a dictionary that looks like:

myDict = { 's1' : ['a', 'c', 'b', 'd'], 
           's2' : ['c', 'd', 'a', 'b'], 
           's3' : ['a', 'b', 'c', 'd'], 
           's4' : ['c', 'a', 'b', 'd'], 
           's5' : ['a', 'b', 'd', 'c'], 
           's6' : ['c', 'a', 'b', 'd'],
           's7' : ['b', 'a', 'a', 'd'],
           's8' : ['c', 'b', 'd', 'a']}

#next I created a new dictionary where the values are listed keys to be filled
newDict = { 'a' : [], 'b' : [], 'c': [], 'd' : [] }

#updating newDict by 1st listed value in myDict
for j in range(1):
    for x in myDict.keys():
        newDict[myDict[x][j]].append(x)

#result
newDict = { 'a' : ['s1', 's3', 's5'], 'b': ['s7'], 'c' : ['s2', 's4', 's6', 's8'], 'd': [] }

Next, I would like to loop where it references the listed values in myDict and fill in the newDict keys so that each key has two values, balancing out by their 'ordered' preference.

This would mean that it would have to reference the second or third listed value from myDict key and update its values throughout to find a balance. For example:

#intended final newDict values
newDict = { 'a' : ['s1', 's5'], 'b': ['s7', 's3'], 'c' : ['s4', 's6'], 'd': ['s2', 's8'] }

Apologies for any mistakes and thanks for the insight

Answer 1

Here's a simple approach to solving your problem by refusing to fill a list in newDict with more than two items. It is probably not quite optimal, since it awards the "first choice" spots based on a first-come-first-served basis, without considering which second choices are easier to fill than others. It does however consider all first place picks first, then all second place picks, then third, etc.

from collections import defaultdict, deque

myDict = { 's1' : ['a', 'c', 'b', 'd'], 
           's2' : ['c', 'd', 'a', 'b'], 
           's3' : ['a', 'b', 'c', 'd'], 
           's4' : ['c', 'a', 'b', 'd'], 
           's5' : ['a', 'b', 'd', 'c'], 
           's6' : ['c', 'a', 'b', 'd'],
           's7' : ['b', 'a', 'a', 'd'],
           's8' : ['c', 'b', 'd', 'a']}

newDict = defaultdict(list)

to_assign = deque(myDict.items())          # Start with a queue of all of myDict's items
while to_assign:
    key, value = to_assign.popleft()       # Take an item off the queue
    if len(newDict[value[0]]) < 2:         # See if its first pick is available
        newDict[value[0]].append(key)      # If so, add it to the result
    else:                                  # Otherwise, put the item on the
        to_assign.append((key, value[1:])) # end of the queue with its first pick removed

Answer 2

Here is one possible implementation of the result you desire

myDict = { 's1' : ['a', 'c', 'b', 'd'], 
           's2' : ['c', 'd', 'a', 'b'], 
           's3' : ['a', 'b', 'c', 'd'], 
           's4' : ['c', 'a', 'b', 'd'], 
           's5' : ['a', 'b', 'd', 'c'], 
           's6' : ['c', 'a', 'b', 'd'],
           's7' : ['b', 'a', 'a', 'd'],
           's8' : ['c', 'b', 'd', 'a']}

options = ['a', 'b', 'c', 'd']
newDict = {option: [] for option in options}
for key, value in myDict.items():
    newDict[value[0]].append(key)

# balance out the dictionary
desired_length = 2
while True:
    for key, value in newDict.items():
        if len(value) > desired_length:
            popped = value.pop()
            new_index = myDict[popped].index(key) + 1
            new_key = myDict[popped][new_index]
            print('Move {} from {} to {}'.format(popped, key, new_key))
            newDict[new_key].append(popped)
    if all(len(value) == desired_length for value in newDict.values()):
        break
print(newDict)

Output:

Move s4 from c to a
Move s4 from a to b
Move s6 from c to a
Move s6 from a to b
Move s6 from b to d
Move s5 from a to b
Move s5 from b to d
{'d': ['s6', 's5'], 'b': ['s7', 's4'], 'c': ['s8', 's2'], 'a': ['s3', 's1']}

This is not "optimal" in any sense (though I don't even know what you would consider optimal), nor is it even guaranteed to return a useful result (it's conceivable that we could run out of a/b/c/d options for a given s# and thus walk off the end of a list), nor is it deterministic (since order of iteration for dictionaries can vary from run to run), but perhaps it will give you some idea of where to start, and where you need to understand your goal better.