473,703 Members | 2,369 Online

# Find pairs that occur in two or more sets

I have n sets of elements. I want to find elements that occur more than once
in more than one set.

Maybe the following example shows what I mean:

S1 = {1,2,3,2,4}
S2 = {2,2,4,5,4}
S2 = {2,5,2}

The algorithm should find that the "2" occurs more than once in S1, S2, and
S3 (it should also give me the position of the "2" in each of these sets).
All the other members are irrelevant (the "4", for example), since for them
it is not true that they occur more than once in two or more sets.

What is the most efficient way to do this? It is maybe more a general
computer science question, but maybe there are STL tricks that could be
useful in computing this?

Markus

Jul 23 '05 #1
6 1702

"Markus Dehmann" <ma************ @gmail.com> wrote in message
news:37******** *****@individua l.net...
I have n sets of elements. I want to find elements that occur more than once in more than one set.

Maybe the following example shows what I mean:

S1 = {1,2,3,2,4}
S2 = {2,2,4,5,4}
S2 = {2,5,2}

The algorithm should find that the "2" occurs more than once in S1, S2, and S3 (it should also give me the position of the "2" in each of these sets).
All the other members are irrelevant (the "4", for example), since for them it is not true that they occur more than once in two or more sets.

What is the most efficient way to do this? It is maybe more a general
computer science question, but maybe there are STL tricks that could be
useful in computing this?

Maybe the following hints can get you started ... if you think it sounds
useful, try writing the program and post code here if you get stuck. We'll
give you more help.

1) use a std::multimap with the values (e.g. 2 and 4 from your example), as
the keys.

2) create a struct to keep track of the set ID and the positions of the
values in each set. Use objects of this type to represent the values in the
multimap.

3) search the multimap and see which keys have more than one value
associated with them.

HTH,

Dave Moore
Jul 23 '05 #2
Markus Dehmann wrote:
I have n sets of elements. I want to find elements that occur more than once
in more than one set.

Maybe the following example shows what I mean:

S1 = {1,2,3,2,4}
S2 = {2,2,4,5,4}
S2 = {2,5,2}

The algorithm should find that the "2" occurs more than once in S1, S2, and
S3 (it should also give me the position of the "2" in each of these sets).
All the other members are irrelevant (the "4", for example), since for them
it is not true that they occur more than once in two or more sets.

What is the most efficient way to do this? It is maybe more a general
computer science question, but maybe there are STL tricks that could be
useful in computing this?

If you have very large unsorted arrays, you could use std::sort and a
special comparator functor, or perhaps a radix sort if your key space is
efficiently mapped to integers.

So, are the values in your arrays bounded ?
Jul 23 '05 #3
Gianni Mariani wrote:
Markus Dehmann wrote:
I have n sets of elements. I want to find elements that occur more than
once in more than one set.

Maybe the following example shows what I mean:

S1 = {1,2,3,2,4}
S2 = {2,2,4,5,4}
S2 = {2,5,2}

The algorithm should find that the "2" occurs more than once in S1, S2,
and S3 (it should also give me the position of the "2" in each of these
sets). All the other members are irrelevant (the "4", for example), since
for them it is not true that they occur more than once in two or more
sets.

What is the most efficient way to do this? It is maybe more a general
computer science question, but maybe there are STL tricks that could be
useful in computing this?

If you have very large unsorted arrays, you could use std::sort and a
special comparator functor, or perhaps a radix sort if your key space is
efficiently mapped to integers.

So, are the values in your arrays bounded ?

The values are not bounded. And they are not integers in my real example,
but there is a way to sort them if necessary.

Markus

Jul 23 '05 #4
Dave Moore wrote:

"Markus Dehmann" <ma************ @gmail.com> wrote in message
news:37******** *****@individua l.net...
I have n sets of elements. I want to find elements that occur more than

once
in more than one set.

Maybe the following example shows what I mean:

S1 = {1,2,3,2,4}
S2 = {2,2,4,5,4}
S2 = {2,5,2}

The algorithm should find that the "2" occurs more than once in S1, S2,

and
S3 (it should also give me the position of the "2" in each of these
sets). All the other members are irrelevant (the "4", for example), since
for

them
it is not true that they occur more than once in two or more sets.

What is the most efficient way to do this? It is maybe more a general
computer science question, but maybe there are STL tricks that could be
useful in computing this?

Maybe the following hints can get you started ... if you think it sounds
useful, try writing the program and post code here if you get stuck.
We'll give you more help.

1) use a std::multimap with the values (e.g. 2 and 4 from your example),
as the keys.

2) create a struct to keep track of the set ID and the positions of the
values in each set. Use objects of this type to represent the values in
the multimap.

3) search the multimap and see which keys have more than one value
associated with them.

Good idea, thanks!

Markus

Jul 23 '05 #5
> I have n sets of elements. I want to find elements that occur more than
once in more than one set.

The usual definition of a set is that any particular value occurs at most
once in a particular set. So as stated, this problem is trivial.

I suggest restating the problem more accurately before looking for
solutions.
Jul 23 '05 #6
Andrew Koenig wrote:
I have n sets of elements. I want to find elements that occur more than
once in more than one set.

The usual definition of a set is that any particular value occurs at most
once in a particular set. So as stated, this problem is trivial.

I suggest restating the problem more accurately before looking for
solutions.

s/set/multiset/g;

Markus

Jul 23 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.