2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Right off the top of my head this sounds like it's linked to graph coloring. $\endgroup$ – Draconis Oct 8 '18 at 5:59
  • $\begingroup$ Either your pseudocode or your implementation has a bug. A good first step would be to use the unit tests to find it. $\endgroup$ – Yuval Filmus Oct 8 '18 at 6:59
  • $\begingroup$ @YuvalFilmus I corrected the implementation so my Unit Tests pass. Open issues are: Is there a standardized algorithm for this problem and did I miss some edge cases? $\endgroup$ – Creepin Oct 8 '18 at 7:54
  • $\begingroup$ @Draconis I will have a look at this, thanks! $\endgroup$ – Creepin Oct 8 '18 at 7:54
1
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ Thanks! You are right with your clarification. And you are also right, that my tests fail with this example in certain orders of the key. That's great to have a failing test now, I can focus on. I am looking into your states algorithms, but havn't found a possibility to keep multiple values per key yet. I will dig deeper into these algorithms and the nomenclature to see if I can alter them. $\endgroup$ – Creepin Oct 8 '18 at 15:45
  • $\begingroup$ Welcome! A simple stupid way to keep multiple values is, after getting a maximal matching, doing a full search for each key to recover other keys that can be preserved, assuming you have a copy of the original dictionary preserved. $\endgroup$ – Apass.Jack Oct 8 '18 at 16:04
  • $\begingroup$ Yes that is what came to my mind just after leaving work! I will implement that tomorrow, I think that will completely suffice my needs. $\endgroup$ – Creepin Oct 8 '18 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.