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)
Here is one approach:
struct Set
{
int num_elems;
int *elems; // array containing elements.
int counter; // initially zero.
Set *link;
};
struct
{
// number of sets containing index of
// this array element.
int num_cointaining_sets;
// array of pointers to containing sets.
Set **containing;
}
containing_set[MAX_ELEM];
FOR each integer in input set
FOR each set pointed to by "containing" array
IF counter == 0
put set struct in a linked list (using "link" member)
ENDIF
counter = counter + 1
ENDFOR
ENDFOR
FOR each set in the link list constructed above
IF counter == num_elems
print set
ENDIF
counter = 0
ENDFOR
Clearly this has very bad worst-case
time/space behavior. I suspect it may
be a good solution in some
"average" case, but it's beyond me
to back that suspicion up mathematically.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
