Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Go

Idiom #218 List intersection

Create the list c containing all unique elements that are contained in both lists a and b.
c should not contain any duplicates, even if a and b do.
The order of c doesn't matter.

func intersection[S ~[]T, T comparable](a, b S) S {
	seta := make(map[T]bool, len(a))
	for _, x := range a {
		seta[x] = true
	}
	setb := make(map[T]bool, len(b))
	for _, y := range b {
		setb[y] = true
	}

	var c S
	for x := range seta {
		if setb[x] {
			c = append(c, x)
		}
	}
	return c
}

Convert to sets, then iterate in one pass.
The runtime cost is O(n).
The final order is indeterminate.
Works for any type parameter T.
func intersection[S ~[]T, T comparable](a, b S) S {
	s, l := a, b
	if len(b) < len(a) {
		s, l = b, a
	}

	set := make(map[T]struct{}, len(s))
	for _, x := range s {
		set[x] = struct{}{}
	}

	c := make(S, 0, len(s))
	for _, x := range l {
		if _, found := set[x]; found {
			c = append(c, x)
			delete(set, x)
		}
	}
	return c
}

Convert the smallest slices to a set, then iterate on the other slice to see which elements are also in the set.
Duplicate elements are ignored.
The final order is indeterminate.
Works for any comparable type T.


Complexity: O(N) [N = len(a)+len(b)]
Memory: O(N) [N = min(len(a), len(b)]
seta := make(map[T]bool, len(a))
for _, x := range a {
	seta[x] = true
}
setb := make(map[T]bool, len(a))
for _, y := range b {
	setb[y] = true
}

var c []T
for x := range seta {
	if setb[x] {
		c = append(c, x)
	}
}

Convert to sets, then iterate in one pass.
The runtime cost is O(n).
Elements have type T.
The final order is indeterminate.
(def c (clojure.set/intersection (set a) (set b)))
New implementation...
< > ⌨
programming-idioms.org 
func intersection[S ~[]T, T comparable](a, b S) S {
	seta := make(map[T]bool, len(a))
	for _, x := range a {
		seta[x] = true
	}
	setb := make(map[T]bool, len(b))
	for _, y := range b {
		setb[y] = true
	}

	var c S
	for x := range seta {
		if setb[x] {
			c = append(c, x)
		}
	}
	return c
}
func intersection[S ~[]T, T comparable](a, b S) S {
	s, l := a, b
	if len(b) < len(a) {
		s, l = b, a
	}

	set := make(map[T]struct{}, len(s))
	for _, x := range s {
		set[x] = struct{}{}
	}

	c := make(S, 0, len(s))
	for _, x := range l {
		if _, found := set[x]; found {
			c = append(c, x)
			delete(set, x)
		}
	}
	return c
}
seta := make(map[T]bool, len(a))
for _, x := range a {
	seta[x] = true
}
setb := make(map[T]bool, len(a))
for _, y := range b {
	setb[y] = true
}

var c []T
for x := range seta {
	if setb[x] {
		c = append(c, x)
	}
}
(def c (clojure.set/intersection (set a) (set b)))
c = a.Intersect(b).ToList();
C = lists:flatten([A -- B] ++ [B -- A]).
a `intersect` b
const c = [...new Set(a)].filter(e => b.includes(e));
Set<T> A = copyOf(a), B = copyOf(b);
List<T> c = A.stream().filter(B::contains).toList();
a.retainAll(b);
List<T> c = new ArrayList<>(copyOf(a));
a.retainAll(b);
List<T> c = List.copyOf(Set.copyOf(a));
Set<T> A = copyOf(a), B = copyOf(b);
List<T> c = new ArrayList<>();
for (T t : A) if (B.contains(t)) c.add(t);
$c = array_intersect($a, $b)
for elem in a do
  if (b.indexof(elem) >= 0) and (c.indexof(elem) = -1) then
    c.add(elem);
my %u;
$u{$_} = 1 for @a, @b;
my @c = keys %u;
c = list(set(a) & set(b))
c = list(set(a).intersection(b))
c = [*{*a} & {*b}]
c = a & b
let set_a: HashSet<_> = a.into_iter().collect();
let set_b: HashSet<_> = b.into_iter().collect();
let c = set_a.intersection(&set_b);
let unique_a = a.iter().collect::<HashSet<_>>();
let unique_b = b.iter().collect::<HashSet<_>>();

let c = unique_a.intersection(&unique_b).collect::<Vec<_>>();