Stack Overflow
Stack Overflow

Questions tagged [set-intersection]

The intersection of two or more sets consists of the elements that those sets all have in common.

Set intersection is a mathematical operation defined upon sets.
The intersection of two or more sets is defined as the set of those elements that are present in all sets.

For example, let A = { 2, 3, 4 } and B = { 2, 4, 5 }.
The intersection of A and B is what the set of elements that A and B have in common: { 2, 4 }.
The symbol for intersection is ∩, so in our example we would write A ∩ B = { 2, 4 }

276 questions
383
votes
7 answers

Best way to find the intersection of multiple sets?

I have a list of sets: setlist = [s1,s2,s3...] I want s1 ∩ s2 ∩ s3 ... I can write a function to do it by performing a series of pairwise s1.intersection(s2), etc. Is there a recommended, better, or built-in way?
user116293
  • 5,534
  • 4
  • 25
  • 17
83
votes
15 answers

Efficient list intersection algorithm

Given two lists (not necessarily sorted), what is the most efficient non-recursive algorithm to find the set intersection of those lists? I don't believe I have access to hashing algorithms.
David
54
votes
19 answers

Python: simple list merging based on intersections

Consider there are some lists of integers as: #-------------------------------------- 0 [0,1,3] 1 [1,0,3,4,5,10,...] 2 [2,8] 3 [3,1,0,...] ... n [] #-------------------------------------- The question is to merge lists having at least one common…
Developer
  • 8,258
  • 8
  • 49
  • 58
51
votes
7 answers

Difference and intersection of two arrays containing objects

I have two arrays list1 and list2 which have objects with some properties; userId is the Id or unique property: list1 = [ { userId: 1234, userName: 'XYZ' }, { userId: 1235, userName: 'ABC' }, { userId: 1236, userName: 'IJKL' }, {…
Shashi
  • 1,112
  • 2
  • 17
  • 32
47
votes
6 answers

Intersection of java.util.Map

Is there a method in java.util.Map or any util to perform an intersection on two maps? (To intersect two maps by the "keys") I am not able to find any. I can always implement my own intersection logic, but I was hoping there is already some…
mandy
  • 735
  • 1
  • 9
  • 24
46
votes
5 answers

Union or intersection of Java Sets

What is the simplest way to make a union or an intersection of Sets in Java? I've seen some strange solutions to this simple problem (e.g. manually iterating the two sets).
Mahozad
  • 18,032
  • 13
  • 118
  • 133
45
votes
6 answers

Computing set intersection in linear time?

Is there an algorithm that, given two sets, computes their intersection in linear time? I can run two for loops to check all pairs of elements, recording elements that I find in both of the sets. However, the runninng time will be O(n2). How do I…
NEO
  • 459
  • 1
  • 5
  • 7
40
votes
2 answers

PostgreSQL check if array contains any element from left-hand array

I know that in PostgreSQL you can run a query like: SELECT (1 = ANY('{1,3,4,7}'::int[])) AS result to check if the right-hand array contains the element 1. I was wondering if there is an easy way to check if the right-hand array contains any element…
Lander
  • 3,369
  • 2
  • 37
  • 53
23
votes
4 answers

Can I check if a list contains any item from another list?

using Python, I want to check if a list contains an item/value that is also present in another list. For example, here is what I am trying to do: list1 = ['item1','item2','item3'] list2 = ['item4','item5','item3'] if list1 contains any items also…
ShakeyGames
  • 277
  • 1
  • 3
  • 11
21
votes
2 answers

Intersection of lists in R

Is there a function that receives a list x and returns a list y such that y[[i]] = intersect(x[[1]][[i]], x[[2]][[i]], ...) ? If not, is there a R way to code it in a couple of lines?
gappy
  • 10,095
  • 14
  • 54
  • 73
20
votes
3 answers

Java Collections - Quickest way to find if there is a Common element between two Sets

I have two sets from Guava HashMultimap.values(). I need to find out if there's an intersection of these two non-empty sets with the best possible time complexity. I don't need to know about the common elements, just if there's at least one common…
uncaught_exceptions
  • 21,712
  • 4
  • 41
  • 48
19
votes
6 answers

Fastest Set Operations In The West

I haven't been able to find any satisfactory coverage of this topic all in one place, so I was wondering: What are the fastest set intersect, union, and disjoin algorithms? Are there any interesting ones with limited domains? Can anyone beat O(Z)…
Jake Kurzer
  • 1,532
  • 4
  • 16
  • 25
17
votes
1 answer

How do I check if one vector is a subset of another?

Currently, I think my best option is to use std::set_intersection, and then check if the size of the smaller input is the same as the number of elements filled by set_intersection. Is there a better solution?
deworde
  • 2,679
  • 5
  • 32
  • 60
16
votes
3 answers

Trying to understand "except all" in sql query

I came across this example and I don't understand what it means. (SELECT drinker FROM Frequents) EXCEPT ALL (SELECT drinker FROM Likes); relations: Frequents(drinker, bar), Likes(drinker, beer) What does the ALL do in this case? How is the…
user234159
  • 888
  • 3
  • 7
  • 19
16
votes
3 answers

Pairwise Set Intersection in Python

If I have a variable number of sets (let's call the number n), which have at most m elements each, what's the most efficient way to calculate the pairwise intersections for all pairs of sets? Note that this is different from the intersection of all…
ankushg
  • 1,632
  • 4
  • 17
  • 22
1
2 3
…
18 19