Stable marriage algorithm variation

Question

First, I tried to make a simple “stable marriage” algorithm. The programming language is Python 3.

I have a variable named "wanteds" which is a list of numbers. This listing is size N.

For example:

wanteds = [35, 76, 88, 76, 27, 98, 29, 88, 88, 71, 88, 93, 26, 26, 8]

I then have another variable named "preferences" which is a dictionary. The dictionary has N keys (the same N as for the size of "wanteds"). The keys of the "preferences" dictionary are unique names (here letters of the alphabet). Each key in the “preferences” dictionary is assigned a list of numbers. The list can be of variable size (0 to infinity) and include numbers that may or may not be in the number list of the "wanteds" variable. For example:

 preferences = {'A': [34, 76, 59], 'B': [22, 27], 'C': [27, 22], 'D': [23], 'E': [24], 'F': [25], 'G': [26], 'H': [27], 'I': [28], 'J': [29], 'K': [30 ], 'L': [31], 'M': [32], 'N': [33], 'O': [34]}

It should be noted that, for example the key "A" of "preferences", the order of the elements in the list [34, 76, 59] is important. It is said that the number 34 is preferred to the number 76, which is itself preferred to the number 59.

The following algorithm returns a dictionary comprising as keys the N keys of the "preferences" dictionary, and as the value of each key a unique number. This number can be part of its initial number list in "preferences" if it was in the "wanted" list. Otherwise this number is -1. All this while following the priority/preference rules. (I feel like I haven't properly explained this in this paragraph but I hope you understand with the example).

Note that the numbers in the "wanted" list can only be used once.

For final example, with the following variables:

wanted = [35, 76, 88, 76, 27, 98, 29, 88, 88, 71, 88, 93, 26, 26, 8]

preferences = {'A': [34, 76, 59], 'B': [22, 27], 'C': [27, 22], 'D': [23], 'E': [24] , 'F': [25], 'G': [26], 'H': [27], 'I': [28], 'J': [29], 'K': [30], ' L': [31], 'M': [32], 'N': [33], 'O': [34]}

I obtain as result:

 {'A': 76, 'B': -1, 'C': 27, 'D': -1, 'E': -1, 'F': -1, 'G' : 26, 'H': -1, 'I': -1, 'J': 29, 'K': -1, 'L': -1, 'M': -1, 'N': -1 , 'O': -1}

Explanations: "A" has 76 because 34 does not exist in "wanteds". Even if "B" wanted 27, "C" gets it because "C" wanted 27 in the first position while "B" wanted 27 in the second position, so "C" has 27 and B has -1. Even if "H" wanted 27, since "C" already has 27 and 27 only appears once in "wanteds", there is no 27 available for "H", so "H" has -1 . And "C" and "H" wanted the number 27 with the same "importance/priority", si 27 stays with "C".

Program: The following program allows (I hope) to make the problem mentioned above work correctly. It is certainly not the optimal solution:

def stable_matching(wanteds: list, preferences: dict):
    result = {}

    for preference_name, preference_numbers in preferences.items():
        for preference_number in preference_numbers:
            if preference_number in wanteds:
                wanteds.remove(preference_number)
                result[preference_name] = (preference_number, preference_numbers.index(preference_number))
                break
        
            current_preference_name_preference_number_index = preference_numbers.index(preference_number)
            for old_result_name, old_result_made in result.items():
                if old_result_made[0] == preference_number and old_result_made[1] > current_preference_name_preference_number_index:
                    result[preference_name] = (preference_number, preference_numbers.index(preference_number))
                    result.pop(old_result_name)
                    break

    for preference_name, preference_numbers in preferences.items():
        if preference_name not in result:
            result[preference_name] = -1
        else:
            result[preference_name] = result[preference_name][0]

    return dict(sorted(result.items()))

wanteds = [35, 76, 88, 76, 27, 98, 29, 88, 88, 71, 88, 93, 26, 26, 8]
# wanteds = [[35, 28], [76], [88], [76], [27], [98], [29], [88], [88], [71], [88], [93], [26], [26], [8]]
preferences = {'A': [34, 76, 59], 'B': [22, 27], 'C': [27, 22], 'D': [23], 'E': [24], 'F': [25], 'G': [26], 'H': [27], 'I': [28], 'J': [29], 'K': [30], 'L': [31], 'M': [32], 'N': [33], 'O': [34]}
result = stable_matching(wanteds, preferences)
print(result)

Where I need help: I would like to make the form of the "wanteds" variable more complex :

Before:

[35, 76, 88, 76, 27, 98, 29, 88, 88, 71, 88, 93, 26, 26, 8]

After:

[[35, 28], [76], [88], [76], [27], [98], [29], [88], [88], [71], [88], [ 93], [26], [26], [8]]

"wanted" is now a list of list of numbers. The sublists have a size from 1 to infinity. Why this, I will give an example. the number 35 in the list [35, 28] failed to be assigned, so the program would have to attempt to assign the number 28. the assignment of the number 28 must follow the priority rules of the first version (example with "B", "C" and "H" who wanted the number 27 existing in a single copy). Be careful, it is possible that going from 35 to 28 requires re-evaluating certain couples that were formed earlier.

With this new "wanteds", the result should be the following:

{'A': 76, 'B': -1, 'C': 27, 'D': -1, 'E': -1, 'F ': -1, 'G': 26, 'H': -1, 'I': 28, 'J': 29, 'K': -1, 'L': -1, 'M': -1 , 'N': -1, 'O': -1}

I thank you in advance for your help.

Answer 1

My suggestion is this:

def stable_matching(wanteds: list, preferences: dict):
    result = {}

    for preference_name, preference_numbers in preferences.items():
        for preference_number in preference_numbers:
            if preference_number in wanteds:
                wanteds.remove(preference_number)
                result[preference_name] = (preference_number, preference_numbers.index(preference_number))
                break
        
            current_preference_name_preference_number_index = preference_numbers.index(preference_number)
            for old_result_name, old_result_made in result.items():
                if old_result_made[0] == preference_number and old_result_made[1] > current_preference_name_preference_number_index:
                    result[preference_name] = (preference_number, preference_numbers.index(preference_number))
                    result.pop(old_result_name)
                    break

    for preference_name, preference_numbers in preferences.items():
        if preference_name not in result:
            result[preference_name] = -1
        else:
            result[preference_name] = result[preference_name][0]

    return dict(sorted(result.items()))

def preprocess (wanteds: list, preferences: dict):
    new_wanteds = []
    expand_preference = {}
    for group in wanteds:
        if 0 < len(group):
            new_wanteds.extend(group)
            expand_preference[group[0]] = group
    new_preferences = {}
    for letter, prefer in preferences.items():
        new_prefer = []
        for value in prefer:
            if value in expand_preference:
                new_prefer.extend(expand_preference[value])
        new_preferences[letter] = new_prefer
    return new_wanteds, new_preferences

def new_stable_matching(wanteds: list, preferences: dict):
    new_wanteds, new_preferences = preprocess(wanteds, preferences)
    return stable_matching(new_wanteds, new_preferences)