Remove duplicates from dictionary in a safe and clever way

Question

I have a dictionary that has keys and multiple values per key. Same value can be assigned to multiple keys.

For the sake of simplicity, the keys are ints and the values are strings, so that it would look like in C#:

Dictionary<int,string[]>

As an example the dictionary is filled as follows:

{ 1, ["A","B"] },
{ 2, ["A"] } 

I now have to remove duplicate values, under the condition that each key keeps at least one value (if at all possible).

So we cannot say 1 gets A, because 2 will then have no associated value anymore.

The result for the example should be:

{ 1, ["B"] },
{ 2, ["A"] } 

Another example with result:

{ 1, ["A", "B"] },
{ 2, ["C", "D"] }
-->
{ 1, ["A", "B"] },
{ 2, ["C", "D"] }

One key cannot contains multiples times the same value, so the following scenario is not considered, it cannot happen:

{ 1, ["B"] },
{ 2, ["A", "A"] } 

What I tried so far, but where I am not sure if I captured all edge cases or if there are more efficient or more logic ways:

1. If a key has only one value assigned, this is fixed. The value is removed from all other keys and the key value pair is removed from the iterating list and stored elsewhere

   1.1 If after that removal one key does not have any values associated, the algorithm failed, it is not possible.

   1.2 Repeat 1. until no key with only a single value is left.

2. Search for values that are only assigned to one key. The key value pair is removed from the iterating list and stored elsewhere

3. Repeat 1. to 2. until 2. does not find a result

4. No we have a list with only n to n relations. All keys have at least 2 values and each value is at least assigned to 2 keys.

5. Now we randomly remove one value from a single key.

6. Repeat 1. to 5. until nothing changes anymore.

Is there a standard algorithm for this requirement? I am still not sure if I considered all edge cases.

Answer 1

Your question is very well written. Let me make one requirement even clearer. "Remove duplicate values" means that one value can be assigned to at most one key in the end, as explained in the given examples.

Your algorithm might return the wrong result. For example, consider the following dictionary.

{ 1, ["A", "B"] } 
{ 2, ["A", "B"] },
{ 3, ["C", "A", "B"] },
{ 4, ["D", "A", "B"] } 
{ 5, ["C", "D", "E", "F"] } 
{ 6, ["C", "D", "E", "F"] },

Your algorithm might proceed to remove value "C" from key 3 followed by removing value "D" from key 4. You can check that each keys still has at least 2 values and each value is still at least assigned to 2 keys. However, you can see that key 1, 2, 3 and 4 have two values in total, "A" and "B". So it is not possible to assign each of those four keys with a different value. However, there is an assignment that is possible in the beginning, i.e., { 1, ["A"] }, { 2, ["B"] }, { 3, ["C"] }, { 4, ["D"] }, { 5, ["E"] } and { 6, ["F"] }.

---

The problem you are trying to solve is fundamentally finding the maximal matching in unweighted bipartite graphs. You can find various algorithms given in that Wikipedia page such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. I will let you figure out how to adjust or extend those algorithms a bit to solve your task of "removing duplicates from dictionary".