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. Show how to support UNION in O(1) time using a suitable list data structure.
UNION of two lists
2
$\begingroup$
algorithms
-
3First, your question belongs to http://programmers.stackexchange.com . Second, it obviously depends on how do you implement a set and on what operations performance do you measure (e.g. what if c3 = UNION(c1, c2) executes in O(1), but any operation on c3 executes on O(n!)?( – 2012-07-03
-
0Well, of course it depends and I believe we should choose a suitable list data structure for solving the problem. For example, for a singly linked list I can't find any solution and it's impossible in my humble opinion. I'll try to ask on programmers.stackexchange.com if there is wrong place for my question, sorry. – 2012-07-03
-
2@penartur: programmers.SE is definitely not the place -- that site is for question about programming as a job/social/business activity rather than about particular technical questions. The question might be relevant at the CS site (but in my opinion that doesn't prevent the topic from being welcome here, too). – 2012-07-03
-
0Henning Makholm - Thank you. I will be glad to discuss it anywhere. – 2012-07-03
1 Answers
1
If all you care about is the union operation and all other operations (such as membership testing) can be as slow as you want to, just concatenate the two linked lists. This can be done in constant time if you make sure to remember a pointer to both the first and the last element of each list. Remember to check whether the two lists are the same.
If there is no requirement that the result must be a list, you could also represent a set as an unordered binary tree with the members in the leaves. Then the union operation consists just of creating a new root node with the two operands as children. And that doesn't even destroy the original sets.
-
1"If all you care about is the union operation and all other operations (such as membership testing) can be as slow as you want to" - then one could implement an UNION operation to be as slow as they like to, and then to expose a lazy (delayed) version of it. This applies to any operations on any types, not only to UNION and sets. With such a specification, the task is pointless. – 2012-07-03
-
0I see your point, but I assume that we no nothing about the tail element of lists (because if we know we will be able to set tail1.next = head2). If I am not mistaken we definately should use some of list data structure.. – 2012-07-03
-
0@Timofei Are common elements not a problem? – 2012-07-03
-
0@Timofei: Where do you get that assumption from? Do you know something extra about the question that you have not shared? If your question is a verbatim quote from an exercise sheet (it could read that way), then "using _a suitable_ list structure" (my emphasis) gives you a wide latitude to choose the _kind_ of list structure you'll use, all the way up to circular doubly-linked lists and wilder things. Merely keeping track of both heads and tails is not some fancy extension that you need special permission to use -- it's a basic setting on the algorithmic tool you're looking at. – 2012-07-03
-
0@penartur: Well, that's essentially what my second suggestion is, except that being even more ruthless than that and leaving all the implementation work to be redone at every single membership test. – 2012-07-03
-
0This question is in the "Introduction to algorithms" by Thomas H. Cormen and i've posted everithing i knew. By the way, if we know all heads and tail, this means, that we can unite every tipe of lists in O(1), can't we? – 2012-07-03
-
0@SaurabhHota What do you mean by "common elements" there? – 2012-07-03
-
0In my opinion the answer should be like: 1. If we use a singly linked list than ... 2. If we use a doubly linked list than ... 3. If we use a singly linked list with sentinels... and so on. But it's also some kind of assumtion :) – 2012-07-03
-
0@Timofei common element-that are both in $S_1$ and $S_2$ don't you have to remove duplicate elements from $S_1 \cup S_2$? – 2012-07-03
-
0@SaurabhHota: Who says the representation of a set has to exclude duplicates? – 2012-07-03
-
0@HenningMakholm No,its not necessary to exclude duplicates.But if it had been a practicle question then excluding duplicates may be important.Since timofei mentioned that that it was a theoretical question from Cormen then any of the linked list or binary tree will work with suitable adjustments. – 2012-07-03
-
0Well, I suppose that we have to know about the tails, otherwise it's impossible to unite (we will lose some data or the order will be incorrect) or we can use some other data structure to store a united set. We don't need to delete duplicates. – 2012-07-03