-2
$\begingroup$

I have a problem that I think should have been studied. I am looking for algorithms for it.

Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items.

Each key and each value can appear multiple times. The number of possible keys and possible values can be arbitrary large.

We are given $x$ and $F$. We want to find all those items $y$ in $F$ such that $y.val \subseteq x$.

For example,

$x = \{(a,1), (b,2), (c,3), (d,4)\}$

$F= \{$
$(A, \{(a,1)\}), $
$(B, \{(a,1), (b,2)\}),$
$(C, \{(a,1), (b,3)\}),$
$(D, \{(b,2), (c,3), (d,4)\}),$
$(E, \{(a,1), (b,2), (c,3), (d,4)\}),$
$(F, \{(a,1), (b,2), (c,3), (d,4), (e,5)\}),$
$(G, \{(a,1), (b,2), (c,3), (e,5)\})$
$\}$

The answer is: $A$ yes, $B$ yes, $C$ no (right keys, wrong values), $D$ yes, $E$ yes (exact match), $F$ no, $G$ no.

Has this problem been studied?

The problem seems similar to finding features from a DNA sequence or detecting plagiarism in a document.

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ Please state the computational problem that you want to solve without code. For example: I am given input [the description of what is given], and I want to compute [the description of what you want to compute]. Check other questions for examples. $\endgroup$
    – Kaveh
    Commented Jun 18, 2013 at 3:18
  • $\begingroup$ Will there generally be a total order on the set of values? $\hspace{2.51 in}$ Will there generally be a total order on the set of keys? $\:$ $\endgroup$
    – user6973
    Commented Jun 18, 2013 at 5:34
  • $\begingroup$ @Kaveh I thought code would be helpful because I'm unfamiliar with the vocabulary used in theoretical computer science. Regardless here's a stab... Given an item defined by an unknown number of key value pairs and a feature set of items defined the same way, find the items in the feature set that are a subset of the given item. Even help defining this problem would be a great help. Thanks $\endgroup$
    – wroscoe
    Commented Jun 18, 2013 at 6:18
  • 1
    $\begingroup$ there is so much extraneous information it seems. why does it matter these are key-value pairs? you have a set $S$ and a collection of sets $\{T_1, ..., T_n\}$, and you want to output all $T_i$ which satisfy $T_i \subseteq S$. the key word for you is hashing. $\endgroup$
    – Sasho Nikolov
    Commented Jun 18, 2013 at 17:32
  • 1
    $\begingroup$ Oh come on..hash each pair in $x$ and store them in the hash table. now for each item in $F$, hash each of its pairs and check if it is equal to a pair in $x$. The expected running time is linear in input size. $\endgroup$
    – Sasho Nikolov
    Commented Jun 19, 2013 at 4:19

1 Answer 1

Reset to default
-1
$\begingroup$

The most straightforward answer I can think of, but unsure about running times:

def find_matching(d, f):
      matching = []
      dSet = set(d.items())
      for k in f:
        if set(f[k].items()).issubset(dSet):
          matching.append(k)
      return matching
Improve this answer
$\endgroup$
2
  • $\begingroup$ 6 character edit requirement $\:$ gaaah $\;\;\;$ $\endgroup$
    – user6973
    Commented Jun 18, 2013 at 7:29
  • $\begingroup$ This is not Stack Overflow. For questions about algorithms you should not assume people know any particular programming language. Please explain your algorithm in plain English or pseudo-code. $\endgroup$
    – Kaveh
    Commented Jun 18, 2013 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.