Algorithm: Given an array inside an array of arrays, how to find subsets of elements that make that array unique or with the smallest match count?

Question

Given

[
["hahaha", "hehehe", "hihihi", "huhuhu"],
["hehe","hehehe","hihi","hihihi"],
["huhuhu","juju","jejejjo"],
["zxcvzxcv","zevaerva","53qgaSD","zvxzr","hahaha"]
]

find subsets of elements in each array , eg take the first one

 ["hahaha", "hehehe", "hihihi", "huhuhu"],

that make it uniquely identifiable in all of the arrays. Eg

["hahaha","huhuhu"]
["hehehe","huhuhu"]

would uniquely identify the first array

 ["hahaha", "hehehe", "hihihi", "huhuhu"],

I have been thinking about this problem for a long time, and it is somewhat akin to LCM, but I guess instead of least common, we would look for the least uncommon elements? Wonder if there is a term in computer science for this problem.

My first approach is generating all variations like this for each array (source https://stackoverflow.com/questions/43241174/javascript-generating-all-combinations-of-elements-in-a-single-array-in-pairs)

  variations = current_array.reduce(
    (acc, v, i) =>
      acc.concat(
        example.wrong.strings[example.error_position]
          .slice(i + 1)
          .map(w => [v, w])
      ),
    []
  );

and looping through with every generated versions the main array of arrays and throwing away subsets that match more than one.

This approach does not seem to scale when arrays have many elements, eg 10+, with thousands of such arrays.

I originally posted this question at Stackoverflow but unsure which site would be a better match.

Big picture: I have been running an online grammar checker for 7 years now at https://proofreadbot.com and started collecting good - bad pair of sentences. Now, if each word is represented as an array with features (eg the sentence pairs "I am like you." "I am liked you."

can be represented as an array of arrays like so

[
"I",
"noun", 
"personal pronoun",
"first_person",
"sentence_start",
"preceded_by_verb",
"preceded_by_present_tense" 
],
[
"am",
"verb", 
"present_tense", 
"preceded_by_noun",
"preceded_by_first_person", 
],    [
"like",
"adverb", 
"preceded_by_present_tense", 
"preceded_by_verb",
"preceded_by_first_person", 
],

...

[
"liked",
"verb", 
"past_tense", 
"preceded_by_noun",
"preceded_by_first_person", 
"contains_error"],



)

Then, I would like to focus on finding the words that have the error. Hope that makes sense. By the way, the first answer by Doc Brown seems great, will give it a shot.

Given hundreds of good pad sentence pairs, there are plenty of items where a subset is tested giving high confidence.

I would guess such an algorithm could be useful for searching through DNA as well and identifying unique strings etc.

Answer 1

Picture it as a graph problem, where every word is a node and nodes are connected with colored edges:

Except that we don't care about ordering, so the graph can be a dictionary with the word as a key and a array or hash set as the value (which contains the sentences' indexes).

If you want to find out how to uniquely identify a sentence, visit every node and create word pairs. For sentence 1 that would be:

{hahaha { 1, 4 }, hehehe { 1, 2 }}, {hahaha { 1,  4 }, hihihi { 1, 3 }}, ...

In the second step you look for set intersections between those pairs. If you only find the starting sentence, you have a match. This step is the actual work but the problem space is now much, much smaller and you can update the data structure incremetally if you need to.

Answer 2

Here is how I would approach this:

• start with the strings from from the first array A

• for each string, count in how many different arrays the string occurs

• pick the string which occurs in as few arrays as possible, lets call it s1

• remove all arrays from the list where s1 does not occur

Now continue with the remaining strings from A and repeat the process: count the occurrences in the remaining set of arrays (which may be already a significantly smaller number), pick the string s2 which occurs in as few remaining arrays as possible, and again remove all arrays which dont contain s2.

When A is the only array left, you have found a solution (s1, s2, ...) which identifies A uniquely. When there are no strings left in A, but still other arrays left, those are the ones which contain all strings in A.

Note the following optimzation: when you repeat the algorithm for another array which contains a string which was already contained in A, you can avoid to count the occurences of that string at the first iteration by memoizing the former result. This might be worth a try, especially when there are often strings which occur only in a few arrays, hence can lower the number of arrays to process in the first step.