Re^4: Mutually Exclusive Elements

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?

Comment on Re^4: Mutually Exclusive Elements

Replies are listed 'Best First'.
Re^5: Mutually Exclusive Elements by dragonchild (Archbishop) on Dec 03, 2004 at 17:28 UTC
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]

Replies are listed 'Best First'.

Re^5: Mutually Exclusive Elements
by dragonchild (Archbishop) on Dec 03, 2004 at 17:28 UTC

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]