Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

(Algorithms) subset finding

  1. Aug 22, 2009 #1
    I have some ideas and a sketch of an algorithm for this problem, but let's see what other people think.

    You have two finite sets of finite sets, S and T. The elements of S and of T are all subsets of another finite set P.

    The problem is: is there any set t in T, such that there is a subset s of t where s is an element of S? And specifically what are the pairs (s,t) for which that is true?

    Some example numbers of the size of problem I want to solve: |P| = 1000, |S| = |T| = 10,000,000

    The brute force way would be to check every pair (s,t) with s in S and t in T, and test whether s is a subset of t. That could take an awfully long time. I have an idea for a more efficient method, but I'm wondering if anybody has encountered this problem before or has an idea how best to solve it.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted