vijay wrote: > Lets say you have a given collection of subsets of a set of integers. > > Given a set of integers as input, what is the most efficient way to > find out all the subsets in the collection of subsets which are also > the subsets of the given set. > > A linear time solution is easy. I was wondering if there is a faster > way to do so. > > So, if given sets > (1,2) (3,4) (2,3) > > and given a input set of (1,2,3), i want the answer to be > (1,2) and (2,3)
If the range of numbers was small (0 - 15), I'd put the sets through a fast distribution count, into their own small array. Each small distribution array would be part of a larger array, which holds them all. Then for each number in the input set, check for a 1 in the given sets distribution array. Example of distribution arrays for the given sets, just showing 0 - 5: 011000 //(1,2) 000110 //(3,4) 001100 //(2,3) If the range of numbers was large, (but not that many sets), I'd "squish" it down into a sparse array, and do (roughly), the same thing. If the quantity of given sets was HUGE, and the overlap of numbers into multiple sets was quite high, I'd look to make a keyed index as well, and then a master "given number" set, to speed things up. But that would be a job for me to code up. Something that was done all the time and in critical high-volume typically, OK. Otherwise, I'd do it the simpler way. Adak --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
