<p>The most straightforward answer I can think of, but unsure about running times:</p>

<pre><code>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
</code></pre>

CC BY-SA 3.0
2013-06-18T17:21:05.663Z
This is not [SO]. For questions about algorithms you should not assume people know any particular programming language. Please explain your algorithm in plain English or pseudo-code.
Kaveh
CC BY-SA 3.0
2013-06-18T07:08:29.057Z
2013-06-18T17:06:18.477Z
2013-06-18T17:06:18.477Z
H Han
<p>I have a problem that I think should have been studied. I am looking for algorithms for it.</p>

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

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

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

<p>For example,</p>

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

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

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

<p>Has this problem been studied?</p>

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

CC BY-SA 3.0
2013-06-18T03:18:10.217Z
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.
Kaveh
CC BY-SA 3.0
2013-06-18T06:18:05.810Z
@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
wroscoe
CC BY-SA 3.0
2013-06-18T06:35:01.247Z
@RickyDemer The keys will all be text values and are unique to a sigle item (aka definition). The values are text or numeric values.
wroscoe
CC BY-SA 3.0
2013-06-18T15:33:30.497Z
@RickyDemer and Kaveh - I understand this is not the type of problem you guys enjoy solving but could you point me in some direction that would take me a step closer to solving it?
wroscoe
CC BY-SA 3.0
2013-06-18T16:49:49.733Z
@wroscoe, I think the down-votes are not because of the problem you want to solve but because of the style you have stated your problem. Remember, this is a *theoretical* computer science Q&A. You need to state your problem in mathematical language and be clear and accessible. For questions about algorithms, you should not assume any particular programming language. I will edit the question based on your comment, feel free to edit further.
Kaveh
CC BY-SA 3.0
2013-06-18T17:29:22.133Z
ps: Asking for code is off-topic here. If you want code you should ask on [SO]. Btw, the question might be more suitable for [cs.se] which has a broader scope. I can migrate it there if you want.
Kaveh
CC BY-SA 3.0
2013-06-18T17:32:50.260Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-06-18T20:00:55.920Z
@Kaveh Thanks for the edit. This is much cleaner.
wroscoe
CC BY-SA 3.0
2013-06-18T20:11:32.643Z
@SashoNikolov Could you suggest something more specific than hashing. I've looked into hashing but couldn't find anything directly relevant.
wroscoe
CC BY-SA 3.0
2013-06-19T04:19:59.513Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-06-19T19:43:00.490Z
It *is* linear time in the input size: for each item $y$ in $F$ check if all pairs in $y$ are in the hash table. ps: this is not really research-level and should be migrated to [cs.se].
Kaveh
<ds.algorithms><ds.data-structures><db.databases>
Find all items which are subsets of an item
wroscoe
# Find all items which are subsets of an item

(Asked by: username_0 on 2013-06-18)

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.

**Tags:** ds.algorithms, ds.data-structures, db.databases

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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  
> **username_0**: @RickyDemer The keys will all be text values and are unique to a sigle item (aka definition). The values are text or numeric values.  
> **username_0**: @RickyDemer and username_1 - I understand this is not the type of problem you guys enjoy solving but could you point me in some direction that would take me a step closer to solving it?  
> **username_1**: @username_0, I think the down-votes are not because of the problem you want to solve but because of the style you have stated your problem. Remember, this is a *theoretical* computer science Q&A. You need to state your problem in mathematical language and be clear and accessible. For questions about algorithms, you should not assume any particular programming language. I will edit the question based on your comment, feel free to edit further.  
> **username_1**: ps: Asking for code is off-topic here. If you want code you should ask on [SO]. Btw, the question might be more suitable for [cs.se] which has a broader scope. I can migrate it there if you want.  
> **username_2**: 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.  
> **username_0**: @username_1 Thanks for the edit. This is much cleaner.  
> **username_0**: @SashoNikolov Could you suggest something more specific than hashing. I've looked into hashing but couldn't find anything directly relevant.  
> **username_2**: 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.  
> **username_1**: It *is* linear time in the input size: for each item $y$ in $F$ check if all pairs in $y$ are in the hash table. ps: this is not really research-level and should be migrated to [cs.se].  

---

## 1 answers

### Answer by username_3 on 2013-06-18. Score: -1

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

> **Comments:**
> **username_1**: This is not [SO]. For questions about algorithms you should not assume people know any particular programming language. Please explain your algorithm in plain English or pseudo-code.  

---

