1

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.

5
  • 1
    Please don't crosspost, even when you are unsure where the question fits best. Please learn more about crossposts in the SE network here
    – Doc Brown
    Feb 1, 2022 at 14:43
  • 2
    My hunch is that there is a combinatorial explosion, and finding the minimal identifying subset for every array becomes prohibitively expensive quickly. You might want to step back a bit and pose the actual problem that you're trying to solve. Currently, this question looks like an X-Y problem, and people aren't often willing to invest much of their time into such problems. However, it is also possible that this maps to a well-understood algorithm which you and I just don't happen to know :-) Feb 1, 2022 at 15:38
  • Thx Doc and Hans, I added a big picture section to explain where I want to use this algo! :)
    – giorgio79
    Feb 1, 2022 at 19:41
  • Actually, I don't know if the algorithmic problem you scetched (and for which I posted an approach) really solves your grammar-checker problem. How do you intend to use this?
    – Doc Brown
    Feb 2, 2022 at 6:00
  • I will try to uniquely identify words that are marked with an error. Hoping they will have a unique subset of features that can identify them. Not sure if I am explaining myself clearly, but let me know which part is unclear. Probably I was thinking about this problem by myself for too long :D
    – giorgio79
    Feb 2, 2022 at 6:38

2 Answers 2

1

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

The problem as a graph 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.

2
  • 1
    Thx got it working with this algo! Much appreciated. It is super fast this way.
    – giorgio79
    Feb 12, 2022 at 17:11
  • Happy to help, was a fun challenge :) Feb 14, 2022 at 15:15
1

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.

2
  • 1
    Consider [1, 2, 3] in the set [[1, 2, 3], [1, 3, 4], [1, 3], [1, 4], [1, 5], [1, 6], [2, 3, 4], [2, 3], [2, 4], [2, 5], [2, 6]]. It can be uniquely identified by [1, 2], but this algorithm would start from "3" as fewer arrays contain that. The ultimate result ([1, 2, 3]) correctly identifies [1, 2, 3] uniquely but not in the smallest way. Feb 3, 2022 at 8:42
  • @JacobRaihle: my algorithm was intended to find a uniquely identifying subset quickly, not necessarily the smallest possible one. I guess "quickly" is more important to the OP than the global optimum.
    – Doc Brown
    Feb 3, 2022 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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