in reply to Re: Mutually Exclusive Elements
in thread Mutually Exclusive Elements

Having single common element is my requirement. You can take that out and calculate 'maximum possible mututally exclusive elments' with minimum number of items in the list as X.

Assume that I have 1000 of such lists. Each list has upto 100 items. I am searching for a particular element. So I like to get all lists which has 'that' element'. Now I don't want to display entire list. I like to list top 10 elements from each list which can represent the relative uniqueness of that particular list compared to others.

Replies are listed 'Best First'.
Re^3: Mutually Exclusive Elements
by dragonchild (Archbishop) on Dec 03, 2004 at 16:39 UTC
    If you're searching for which lists have a certain item, you will want to use a hash for each list. If you don't want to display the whole list, maybe display the name of the list and an option to click through to see the whole list - kind of a summary vs. detail approach.

    Either way, it seems like a lot of work to calculate a rather complicated set-theory value, just for display purposes.

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

[reply]
      The lists do not have 'names' or summary. They have just elements. So elements display is essential. My idea is to find the list where I can add a 'new element'. I can use Hash for each list. It would be nice if display order for mini-lists is 'in the order of insertion in the original lists', but not absolutely necessary.

      I concur that it is a lot of work. Assuming I have L lists, each list has an average of N element and I like to display top T elements, what would be the order of algorithm I should be expecting?

[reply]
        Well, first off, your lists do have a summary - you're trying to figure out how to calculate it. I was hoping you could figure out a cheaper kind of summary. It all depends on if you can precalculate this kind of information or not. If you can precalculate it, then things are a lot cheaper every other time.

        As for algorithms ... you still haven't fully defined the requirements, so you cannot have an algorithm. "Mutually exclusive elements" has a mathematical definition which has nothing to do with minimum numbers ... it has to do with which elements exist in A that don't exist in B, C, or D.

        It sounds like you're trying to find the vector that encompasses the set - the smallest number of elements that uniquely identifies the set vs any other set. That, my friend, is NP-hard in the general case and O(N!) in the specific case. In other words ... find a different solution.

        Being right, does not endow the right to be rude; politeness costs nothing.
        Being unknowing, is not the same as being stupid.
        Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
        Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

[reply]

In Section Seekers of Perl Wisdom