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
6  1686 
"Markus Dehmann" <ma************@gmail.com> wrote in message
news:37*************@individual.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
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 ?
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
Dave Moore wrote:
"Markus Dehmann" <ma************@gmail.com> wrote in message
news:37*************@individual.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
> 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.
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Steven Bethard |
last post by:
So I need to do something like:
for i in range(len(l)):
for j in range(i+1, len(l)):
# do something with (l, l)
where I get all pairs of items in a list (where I'm thinking of pairs
as sets,...
|
by: Xah Lee |
last post by:
suppose you want to do find & replace of string of all files in a
directory.
here's the code:
©# -*- coding: utf-8 -*-
©# Python
©
©import os,sys
©
©mydir= '/Users/t/web'
|
by: les_ander |
last post by:
Hi,
I have 2 lists of tuples that look like:
E1= and
E2=.
In this tuple, the ordering does not
matter, i.e. (u,v) is the same as (v,u).
What I want to do is the following:
given 2 list of...
|
by: pillepop2003 |
last post by:
Hey!
Can anyone give me a hint, how this problem is best implemented:
I have a table of users (see below), where every user has one
"superior user" (= parent node), this should be a fully...
|
by: Jonathan |
last post by:
Hi all!
For a match schedule I would like to find all possible combinations of
teams playing home and away (without teams playing to themselves of course).
I now the simple version works...
|
by: sabarish |
last post by:
Hi to all. find out the biggest among two numbers without using any
conditional statements and any relational operators.
|
by: Evan |
last post by:
Is there a simple way to to identify and remove matching pairs from 2
lists?
For example:
I have
a=
b=
|
by: Alexander Vasilevsky |
last post by:
Here, there is a challenge: to find the files must be on a local computer,
have the same names.
Get drives and folders to go through without problems. But what and how to
store files while a...
|
by: Alan Isaac |
last post by:
I want to generate sequential pairs from a list.
Here is a way::
from itertools import izip, islice
for x12 in izip(islice(x,0,None,2),islice(x,1,None,2)):
print x12
(Of course the print...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |
