Author |
Topic: dynamic-set operation (Read 2109 times) |
|
nks
Junior Member
Gender: 
Posts: 145
|
 |
dynamic-set operation
« on: Jan 28th, 2009, 1:19am » |
 Quote  Modify
|
Question from book of H.Cormen.
The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation.
How to support UNION in O(1) time using a suitable list data structure ?
Can anybody explain the question?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: dynamic-set operation
« Reply #1 on: Jan 28th, 2009, 1:34am » |
Quote Modify
|
on Jan 28th, 2009, 1:19am, nks wrote:The sets S1 and S2 are usually destroyed by the operation.
[..]
Can anybody explain the question? |
|
"Destroying" the input means that you can't depend on it being the same before and after the operation. The operation may change the datastructure it is given as input, and use it for the datastructure of the output; for example what an inplace sort does (there the original input-array is destroyed, in that that the original order is destroyed).
If they're disjoint, you can just join the two lists. L1.last()->next=L2.first();
It may be inconvenient for other operations, though.
|
| « Last Edit: Jan 28th, 2009, 1:42am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: dynamic-set operation
« Reply #2 on: Jan 28th, 2009, 2:06am » |
Quote Modify
|
Is it like how to disjoint the union set after destroying the S1 and S2 ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: dynamic-set operation
« Reply #3 on: Jan 28th, 2009, 2:51am » |
Quote Modify
|
on Jan 28th, 2009, 2:06am, nks wrote:| Is it like how to disjoint the union set after destroying the S1 and S2 ? |
|
I don't understand that sentence; can you rephrase it?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: dynamic-set operation
« Reply #4 on: Jan 28th, 2009, 6:33am » |
Quote Modify
|
I think the question is simply: how to compute the union of 2 sets.
You are asked to describe what list structure is suitable for the task.
You are not requested to preserve the original lists, which means you can take break apart the original lists and reassemble the union from that.
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: dynamic-set operation
« Reply #5 on: Jan 28th, 2009, 10:52pm » |
Quote Modify
|
I think question is making union of 2 sets using these sets so original can be destroyed .
So once union is done it should not depend on original set s1 and s2.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print