How to find Intersection and Union of a List (without using sets)

Question

I am trying to find the intersection and union of two lists for an assignment, however, I cannot use sets. From set theory, an intersection between two sets is the elements that are in both sets. A union is all elements in both sets, without repetition. So far I have:

setA = [1,2,3,4,5,6,7,8,9]
setB = [1,5,0,9]

def getUnion(a, b):
    return a + b

def getIntersection(a, b):
    return

My union function is returning duplicates. Is there a way to simply find the union?

Also, what is the best approach to find the intersection?

Or, if you can't use sets, just use dictionaries: `dict(e: 1 for e in (setA + setB)).keys()` — Robin Davis, Apr 12 '18 at 05:16
Possible duplicate of https://stackoverflow.com/q/2151517/6622817 — Taku, Apr 12 '18 at 05:24

user3483203 · Answer 1 · 2018-04-12T05:45:48.823

Union and intersection without using using sets:

setA = [1,2,3,4,5,6,7,8,9]
setB = [1,5,0,9]

intersection = [i for i in setA if i in setB]
list_union = list({i: i for i in setA + setB}.values())

print(intersection)
print(list_union)

Output:

[1, 5, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

Explanation:

For union:

[i for i in setA if i in setB]

Simply loops through setA and adds elements that are also found in setB

For intersection:

list({i: i for i in setA + setB}.values())

Creates a dictionary where the keys and values are the result of setA + setB. Since keys in a dictionary are unique, duplicates don't show up in the final dictionary, and list(dct.values()) is used to pull just the values needed from the dictionary.

score 0 · Answer 2 · answered Apr 12 '18 at 05:26

So, assume you can use sort. Sort two lists first, then do with two pointers, move one pointer with smaller value forward each time.

For union func, add all values each time and move forward both pointers when their values are equal. For intersection func, only add values when the values are equal.

Time O(nlogn+n)->O(nlogn)

score 0 · Accepted Answer · answered Apr 12 '18 at 05:35

You can use collections.Counter instead to calculate union and intersection

>>> from collections import Counter

>>> c = Counter(setA + setB)
>>> [a[0] for a in c.items() if a[1] > 1] #Intersection
>>> [1,5,9]

>>> list(c.keys()) #Union
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Counter object hold the data in format:

>>> c
>>> Counter({1: 2, 5: 2, 9: 2, 0: 1, 2: 1, 3: 1, 4: 1, 6: 1, 7: 1, 8: 1})

The key is the elements in the list and the value is the occurrence of the element in the list.

score -1 · Answer 4 · answered Apr 12 '18 at 05:17

-1

Try this:

setA = [1,2,3,4,5,6,7,8,9]
setB = [1,5,0,9]

print (list(set(setA).intersection(setB)))

Output:

[1, 5, 9]
[Finished in 0.0s]

answered Apr 12 '18 at 05:17

rahul mehra

418
2
13

1

It says he cannot use sets in the question. – user3483203 Apr 12 '18 at 05:18

How to find Intersection and Union of a List (without using sets)

4 Answers4