Common list elements
Given an integer array nums, find the common list elements.
- Example
nums = [2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9]
output = [3,6,9]
- Metrics
- Counting
- Word frequency
- Letter frequency
- Jewels and stones
- I before E except after C
- Bioinformatics/base count
- Count occurrences of a substring
- Count how many vowels and consonants occur in a string
- Remove/replace
- XXXX redacted
- Conjugate a Latin verb
- Remove vowels from a string
- String interpolation (included)
- Strip block comments
- Strip comments from a string
- Strip a set of characters from a string
- Strip whitespace from a string -- top and tail
- Strip control codes and extended characters from a string
- Anagrams/Derangements/shuffling
- Word wheel
- ABC problem
- Sattolo cycle
- Knuth shuffle
- Ordered words
- Superpermutation minimisation
- Textonyms (using a phone text pad)
- Anagrams
- Anagrams/Deranged anagrams
- Permutations/Derangements
- Find/Search/Determine
- ABC words
- Odd words
- Word ladder
- Semordnilap
- Word search
- Wordiff (game)
- String matching
- Tea cup rim text
- Alternade words
- Changeable words
- State name puzzle
- String comparison
- Unique characters
- Unique characters in each string
- Extract file extension
- Levenshtein distance
- Palindrome detection
- Common list elements
- Longest common suffix
- Longest common prefix
- Compare a list of strings
- Longest common substring
- Find common directory path
- Words from neighbour ones
- Change e letters to i in words
- Non-continuous subsequences
- Longest common subsequence
- Longest palindromic substrings
- Longest increasing subsequence
- Words containing "the" substring
- Sum of the digits of n is substring of n
- Determine if a string is numeric
- Determine if a string is collapsible
- Determine if a string is squeezable
- Determine if a string has all unique characters
- Determine if a string has all the same characters
- Longest substrings without repeating characters
- Find words which contains all the vowels
- Find words which contain the most consonants
- Find words which contains more than 3 vowels
- Find words whose first and last three letters are equal
- Find words with alternating vowels and consonants
- Formatting
- Substring
- Rep-string
- Word wrap
- String case
- Align columns
- Literals/String
- Repeat a string
- Brace expansion
- Brace expansion using ranges
- Reverse a string
- Phrase reversals
- Comma quibbling
- Special characters
- String concatenation
- Substring/Top and tail
- Commatizing numbers
- Reverse words in a string
- Suffixation of decimal numbers
- Long literals, with continuations
- Numerical and alphabetical suffixes
- Abbreviations, easy
- Abbreviations, simple
- Abbreviations, automatic
- Song lyrics/poems/Mad Libs/phrases
- Mad Libs
- Magic 8-ball
- 99 bottles of beer
- The Name Game (a song)
- The Old lady swallowed a fly
- The Twelve Days of Christmas
- Tokenize
- Text between
- Tokenize a string
- Word break problem
- Tokenize a string with escaping
- Split a character string based on change of character
- Sequences
11l
F cle(nums)
V r = Set(nums[0])
L(num) nums[1..]
r = r.intersection(Set(num))
R r
print(cle([[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]]))
- Output:
Set([3, 6, 9])
Action!
INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit
DEFINE PTR="CARD"
PROC PrintArray(BYTE ARRAY a BYTE len)
BYTE i
Print(" [")
IF len>0 THEN
FOR i=0 TO len-1
DO
PrintB(a(i))
IF i<len-1 THEN Put(' ) FI
OD
FI
PrintE("]")
RETURN
BYTE FUNC Contains(BYTE ARRAY a BYTE len,value)
BYTE i,count
count=0
IF len>0 THEN
FOR i=0 TO len-1
DO
IF a(i)=value THEN count==+1 FI
OD
FI
RETURN (count)
PROC CommonListElements(PTR ARRAY arrays
BYTE ARRAY lengths BYTE count
BYTE ARRAY res BYTE POINTER resLen)
BYTE ARRAY a
BYTE i,j,len,value,cnt,maxcnt
resLen^=0
IF count=0 THEN RETURN FI
FOR i=0 TO count-1
DO
IF lengths(i)=0 THEN RETURN FI
OD
a=arrays(0) len=lengths(0)
IF count=1 THEN
MoveBlock(res,a,len) RETURN
FI
FOR i=0 TO len-1
DO
value=a(i)
IF Contains(res,resLen^,value)=0 THEN
maxcnt=Contains(a,len,value)
FOR j=1 TO count-1
DO
cnt=Contains(arrays(j),lengths(j),value)
IF cnt<maxcnt THEN maxcnt=cnt FI
OD
IF maxcnt>0 THEN
FOR j=1 TO maxcnt
DO
res(resLen^)=value resLen^==+1
OD
FI
FI
OD
SortB(res,resLen^,0)
RETURN
PROC Test(PTR ARRAY arrays BYTE ARRAY lengths BYTE count)
BYTE ARRAY res(100)
BYTE len,i
CommonListElements(arrays,lengths,count,res,@len)
PrintE("Input:")
FOR i=0 TO count-1
DO
PrintArray(arrays(i),lengths(i))
OD
PrintE("Intersection:")
PrintArray(res,len) PutE()
RETURN
PROC Main()
PTR ARRAY arrays(3)
BYTE ARRAY
lengths(3)=[8 7 5],
a1(8)=[2 5 1 3 8 9 4 6],
a2(7)=[3 5 6 2 9 8 4],
a3(5)=[1 3 7 6 9],
a4(8)=[2 2 1 3 8 9 4 6],
a5(7)=[3 5 6 2 2 2 4],
a6(5)=[2 3 7 6 2],
a7(5)=[0 1 7 8 9]
BYTE len
Put(125) PutE() ;clear the screen
arrays(0)=a1 arrays(1)=a2 arrays(2)=a3
Test(arrays,lengths,3)
arrays(0)=a4 arrays(1)=a5 arrays(2)=a6
Test(arrays,lengths,3)
arrays(2)=a7
Test(arrays,lengths,3)
RETURN
- Output:
Screenshot from Atari 8-bit computer
Input: [2 5 1 3 8 9 4 6] [3 5 6 2 9 8 4] [1 3 7 6 9] Intersection: [3 6 9] Input: [2 2 1 3 8 9 4 6] [3 5 6 2 2 2 4] [2 3 7 6 2] Intersection: [2 2 3 6] Input: [2 2 1 3 8 9 4 6] [3 5 6 2 2 2 4] [0 1 7 8 9] Intersection: []
Ada
with Ada.Text_Io;
with Ada.Containers.Vectors;
procedure Common is
package Integer_Vectors is
new Ada.Containers.Vectors (Index_Type => Positive,
Element_Type => Integer);
use Integer_Vectors;
function Common_Elements (Left, Right : Vector) return Vector is
Res : Vector;
begin
for E of Left loop
if Has_Element (Right.Find (E)) then
Res.Append (E);
end if;
end loop;
return Res;
end Common_Elements;
procedure Put (Vec : Vector) is
use Ada.Text_Io;
begin
Put ("[");
for E of Vec loop
Put (E'Image); Put (" ");
end loop;
Put ("]");
New_Line;
end Put;
A : constant Vector := 2 & 5 & 1 & 3 & 8 & 9 & 4 & 6;
B : constant Vector := 3 & 5 & 6 & 2 & 9 & 8 & 4;
C : constant Vector := 1 & 3 & 7 & 6 & 9;
R : Vector;
begin
R := Common_Elements (A, B);
R := Common_Elements (R, C);
Put (R);
end Common;
- Output:
[ 3 9 6 ]
ALGOL 68
BEGIN # find common elements of lists #
PRIO COMMON = 1;
# returns the common elements of a and b #
OP COMMON = ( []INT a, b )[]INT:
IF INT a len = ( UPB a - LWB a ) + 1;
INT b len = ( UPB b - LWB b ) + 1;
a len < 1 OR b len < 1
THEN # one or both lists is/are empty #
[]INT()
ELIF a len < b len
THEN # both lists are non-empty, b is shorter #
b COMMON a
ELSE # both lists are non-empty, a is at most as long as b #
[ 1 : b len ]INT result;
[ LWB a : UPB a ]BOOL used;
FOR i FROM LWB a TO UPB a DO used[ i ] := FALSE OD;
INT r pos := 0;
FOR b pos FROM LWB b TO UPB b DO
BOOL found := FALSE;
FOR a pos FROM LWB a TO UPB a WHILE NOT found DO
IF NOT used[ a pos ] THEN
IF ( found := a[ a pos ] = b[ b pos ] ) THEN
result[ r pos +:= 1 ] := b[ b pos ];
used[ a pos ] := TRUE
FI
FI
OD
OD;
result[ : r pos ]
FI # COMMON # ;
# returns the common elements in the lists in nums #
OP COMMON = ( [][]INT nums )[]INT:
IF 1 UPB nums < 1 LWB nums THEN # no lists #
[]INT()
ELIF 1 UPB nums = 1 LWB nums THEN # only one list #
nums[ LWB nums ]
ELSE # two or more lists #
FLEX[ 1 : 0 ]INT result;
result := nums[ LWB nums ] COMMON nums[ LWB nums + 1 ];
FOR i FROM LWB nums + 2 TO UPB nums DO
result := result COMMON nums[ i ]
OD;
result
FI # COMMON # ;
print( ( COMMON [][]INT( ( 2, 5, 1, 3, 8, 9, 4, 6 )
, ( 3, 5, 6, 2, 9, 8, 4 )
, ( 1, 3, 7, 6, 9 )
)
)
)
END
- Output:
+3 +6 +9
APL
APL has the built-in intersection function ∩
∩/ (2 5 1 3 8 9 4 6) (3 5 6 2 9 8 4) (1 3 7 9 6)
3 9 6
AppleScript
AppleScriptObjC
use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later
use framework "Foundation"
use sorter : script "Insertion Sort" -- <https://www.rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript>
on commonListElements(listOfLists)
set mutableSet to current application's class "NSMutableSet"'s setWithArray:(beginning of listOfLists)
repeat with i from 2 to (count listOfLists)
tell mutableSet to intersectSet:(current application's class "NSSet"'s setWithArray:(item i of listOfLists))
end repeat
return (mutableSet's allObjects()) as list
end commonListElements
set commonElements to commonListElements({{2, 5, 1, 3, 8, 9, 4, 6}, {3, 5, 6, 2, 9, 8, 4}, {1, 3, 7, 6, 9}})
tell sorter to sort(commonElements, 1, -1)
return commonElements
- Output:
{3, 6, 9}
Core language only
The requirement for AppleScript 2.3.1 is only for the 'use' command which loads the "Insertion Sort" script. If the sort's instead loaded with the older 'load script' command or copied into the code, this will work on systems as far back as Mac OS X 10.5 (Leopard) or earlier. Same output as above.
use AppleScript version "2.3.1" -- Mac OS X 10.9 (Mavericks) or later.
use sorter : script "Insertion Sort" -- <https://www.rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript>
on commonListElements(listOfLIsts)
script o
property list1 : beginning of listOfLIsts
end script
set common to {}
set listCount to (count listOfLIsts)
repeat with i from 1 to (count o's list1)
set thisElement to {item i of o's list1}
if (thisElement is not in common) then
repeat with j from 2 to listCount
set OK to (item j of listOfLIsts contains thisElement)
if (not OK) then exit repeat
end repeat
if (OK) then set end of common to beginning of thisElement
end if
end repeat
return common
end commonListElements
set commonElements to commonListElements({{2, 5, 1, 3, 8, 9, 4, 6}, {3, 5, 6, 2, 9, 8, 4}, {1, 3, 7, 6, 9}})
tell sorter to sort(commonElements, 1, -1)
return commonElements
Arturo
commonElements: function [subsets][
if zero? size subsets -> return []
if 1 = size subsets -> return first subsets
result: first subsets
loop slice subsets 1 dec size subsets 'subset [
result: intersection result subset
]
return result
]
print commonElements [
[2 5 1 3 8 9 4 6]
[3 5 6 2 9 8 4]
[1 3 7 6 9]
]
- Output:
3 6 9
AutoHotkey
Common_list_elements(nums){
counter := [], output := []
for i, num in nums
for j, d in num
if ((counter[d] := counter[d] ? counter[d]+1 : 1) = nums.count())
output.Push(d)
return output
}
Examples:
nums := [[2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9]]
output := Common_list_elements(nums)
return
- Output:
[3, 6, 9]
AWK
# syntax: GAWK -f COMMON_LIST_ELEMENTS.AWK
BEGIN {
PROCINFO["sorted_in"] = "@ind_num_asc"
nums = "[2,5,1,3,8,9,4,6],[3,5,6,2,9,8,4],[1,3,7,6,9]"
printf("%s : ",nums)
n = split(nums,arr1,"],?") - 1
for (i=1; i<=n; i++) {
gsub(/[\[\]]/,"",arr1[i])
split(arr1[i],arr2,",")
for (j in arr2) {
arr3[arr2[j]]++
}
}
for (j in arr3) {
if (arr3[j] == n) {
printf("%s ",j)
}
}
printf("\n")
exit(0)
}
- Output:
[2,5,1,3,8,9,4,6],[3,5,6,2,9,8,4],[1,3,7,6,9] : 3 6 9
BQN
(∊/⊣)´ ⟨2,5,1,3,8,9,4,6⟩‿⟨3,5,6,2,9,8,4⟩‿⟨1,3,7,6,9⟩
- Output:
⟨ 3 9 6 ⟩
C++
Since lists may contain duplicate items, this example has an additional test with lists containing duplicate items.
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
template <typename T>
void print_vector(const std::vector<T>& list) {
std::cout << "[";
for ( uint32_t i = 0; i < list.size() - 1; ++i ) {
std::cout << list[i] << ", ";
}
std::cout << list.back() << "]";
}
template <typename T>
void print_2D_vector(const std::vector<std::vector<T>>& lists) {
std::cout << "[";
for ( uint32_t i = 0; i < lists.size() - 1; ++i ) {
print_vector(lists[i]); std::cout << ", ";
}
print_vector(lists.back()); std::cout << "]";
}
template <typename T>
std::vector<T> intersection(std::vector<T> a, std::vector<T> b) {
std::vector<T> result = { };
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
return result;
}
int main() {
const std::vector<std::vector<std::vector<int32_t>>> tests = {
{ { 2, 5, 1, 3, 8, 9, 4, 6 }, { 3, 5, 6, 2, 9, 8, 4 }, { 1, 3, 7, 6, 9 } },
{ { 2, 2, 1, 3, 8, 9, 4, 6 }, { 3, 5, 6, 2, 2, 2, 4 }, { 2, 3, 7, 6, 2 } } };
for ( std::vector<std::vector<int32_t>> test : tests ) {
std::vector<int32_t> result = intersection(intersection(test[0], test[1]), test[2]);
std::cout << "intersection of "; print_2D_vector(test);
std::cout << " is: "; print_vector(result); std::cout << std::endl;
}
}
- Output:
intersection of [[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]] is: [3, 6, 9] intersection of [[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]] is: [2, 2, 3, 6]
CLU
contains = proc [T: type] (a: array[T], v: T) returns (bool)
where T has equal: proctype (T,T) returns (bool)
for i: T in array[T]$elements(a) do
if i=v then return(true) end
end
return(false)
end contains
common = proc [T: type] (lists: ssT) returns (sT)
where T has equal: proctype (T,T) returns (bool)
sT = sequence[T]
aT = array[T]
ssT = sequence[sequence[T]]
cur: aT := sT$s2a(ssT$bottom(lists))
for i: int in int$from_to(2, ssT$size(lists)) do
next: aT := aT$[]
for e: T in sT$elements(lists[i]) do
if contains[T](cur, e) then
aT$addh(next,e)
end
end
cur := next
end
return(sT$a2s(cur))
end common
start_up = proc ()
si = sequence[int]
ssi = sequence[sequence[int]]
nums: ssi := ssi$[
si$[2,5,1,3,8,9,4,6],
si$[3,5,6,2,9,8,4],
si$[1,3,7,6,9]
]
po: stream := stream$primary_output()
for i: int in si$elements(common[int](nums)) do
stream$puts(po, int$unparse(i) || " ")
end
end start_up
- Output:
3 6 9
Excel
LAMBDA
Binding the names INTERSECT and INTERSECTCOLS to a pair of lambda expressions in the Excel WorkBook Name Manager:
(See LAMBDA: The ultimate Excel worksheet function)
INTERSECT
=LAMBDA(xs,
LAMBDA(ys,
FILTERP(
LAMBDA(x,
ELEM(x)(ys)
)
)(xs)
)
)
INTERSECTCOLS
=LAMBDA(xs,
IF(1 < COLUMNS(xs),
INTERSECT(
FIRSTCOL(xs)
)(
INTERSECTCOLS(
TAILCOLS(xs)
)
),
xs
)
)
and also assuming the following generic bindings in Name Manager:
ELEM
=LAMBDA(x,
LAMBDA(xs,
ISNUMBER(MATCH(x, xs, 0))
)
)
FILTERP
=LAMBDA(p,
LAMBDA(xs,
FILTER(xs, p(xs))
)
)
FIRSTCOL
=LAMBDA(xs,
INDEX(
xs,
SEQUENCE(ROWS(xs), 1, 1, 1),
1
)
)
TAILCOLS
=LAMBDA(xs,
LET(
n, COLUMNS(xs) - 1,
IF(0 < n,
INDEX(
xs,
SEQUENCE(ROWS(xs), 1, 1, 1),
SEQUENCE(1, n, 2, 1)
),
NA()
)
)
)
- Output:
fx | =INTERSECTCOLS(D2:F9) | ||||||
---|---|---|---|---|---|---|---|
A | B | C | D | E | F | ||
1 | Intersection of three columns | ||||||
2 | 3 | 2 | 3 | 1 | |||
3 | 9 | 5 | 5 | 3 | |||
4 | 6 | 1 | 6 | 7 | |||
5 | 3 | 2 | 6 | ||||
6 | 8 | 9 | 9 | ||||
7 | 9 | 8 | |||||
8 | 4 | 4 | |||||
9 | 6 |
Delphi
const Set1: set of byte = [2,5,1,3,8,9,4,6];
const Set2: set of byte = [3,5,6,2,9,8,4];
const Set3: set of byte = [1,3,7,6,9];
procedure CommonListElements(Memo: TMemo);
{Using Delphi "sets" to find common elements}
var I,Start,Stop: integer;
var Common: set of byte;
var S: string;
begin
{Uses "*" intersection set operator to}
{ find items common to all three sets}
Common:=Set1 * Set2 * Set3;
Memo.Lines.Add('Common Elements in');
Memo.Lines.Add(' [2,5,1,3,8,9,4,6]');
Memo.Lines.Add(' [3,5,6,2,9,8,4]');
Memo.Lines.Add(' [1,3,7,6,9]: ');
S:='';
{Display the common items}
for I:=0 to 9 do
if I in Common then S:=S+IntToStr(I)+',';
Memo.Lines.Add(S);
end;
- Output:
Common Elements in [2,5,1,3,8,9,4,6] [3,5,6,2,9,8,4] [1,3,7,6,9]: 3,6,9, Elapsed Time: 5.260 ms.
DuckDB
This entry provides generic methods for lists of any one DuckDB type.
DuckDB lists
select list_intersect( [2,5,1,3,8,9,4,6], list_intersect([3,5,6,2,9,8,4], [1,3,7,6,9])) as intersection;
- Output:
┌──────────────┐ │ intersection │ │ int32[] │ ├──────────────┤ │ [6, 9, 3] │ └──────────────┘
If order is important, the above can be wrapped in list_sort().
Tables
If the lists are presented as columns in a table, then one can form the disjoint union of the tables (`union all`) and select the items with the requisite multiplicity. Here's an illustration of the method, adapted to accept lists as inputs.
create or replace function intersection(l1,l2,l3) as table (
WITH combined AS (
SELECT unnest(l1) as value
UNION ALL
SELECT unnest(l2)
UNION ALL
SELECT unnest(l3)
)
FROM (FROM combined
GROUP BY value
HAVING COUNT(*) = 3 )
ORDER BY VALUE
);
from intersection([2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9]) as intersection;
- Output:
┌───────┐ │ value │ │ int32 │ ├───────┤ │ 3 │ │ 6 │ │ 9 │ └───────┘
EasyLang
nums[][] = [ [ 2 5 1 3 8 9 4 6 ] [ 3 5 6 2 9 8 4 ] [ 1 3 7 6 9 ] ]
#
found = 1
for e in nums[1][]
for l = 2 to len nums[][]
found = 0
for x in nums[l][]
if e = x
found = 1
break 1
.
.
if found = 0
break 1
.
.
if found = 1
r[] &= e
.
.
print r[]
F#
Of course it is possible to use sets but I thought the idea was not to?
// Common list elements. Nigel Galloway: February 25th., 2021
let nums=[|[2;5;1;3;8;9;4;6];[3;5;6;2;9;8;4];[1;3;7;6;9]|]
printfn "%A" (nums|>Array.reduce(fun n g->n@g)|>List.distinct|>List.filter(fun n->nums|>Array.forall(fun g->List.contains n g)));;
- Output:
[3; 9; 6]
Factor
Note: in older versions of Factor, intersect-all
was called intersection
.
USING: prettyprint sets ;
{ { 2 5 1 3 8 9 4 6 } { 3 5 6 2 9 8 4 } { 1 3 7 6 9 } } intersect-all .
- Output:
{ 3 6 9 }
FreeBASIC
dim as integer nums(1 to 3, 1 to 8) = {{2,5,1,3,8,9,4,6}, {3,5,6,2,9,8,4}, {1,3,7,6,9} }
redim as integer outp(0)
dim as integer i, j
dim as boolean found
function is_in( s() as integer, n as integer, r as integer ) as boolean
for i as uinteger = 1 to ubound(s,2)
if s(r,i)=n then return true
next i
return false
end function
for i = 1 to 8
found = true
for j = 2 to 3
if not is_in( nums(), nums(1,i), j ) then found = false
next j
if found then
redim preserve as integer outp(1 to 1+ubound(outp))
outp(ubound(outp)) = nums(1,i)
end if
next i
for i = 1 to ubound(outp)
print outp(i);" ";
next i
- Output:
3 9 6
FutureBasic
local fn FindCommonElements( arrayOfArrays as CFArrayRef ) as CFStringRef
CFMutableSetRef common = fn MutableSetWithArray( fn ArrayFirstObject( arrayOfArrays ) )
CFRange range = fn CFRangeMake( 1, fn ArrayCount( arrayOfArrays ) - 1 )
CFArrayRef array, arrays = fn ArraySubarrayWithRange( arrayOfArrays, range )
for array in arrays
MutableSetIntersectSet( common, fn SetWithArray( array ) )
next
CFArrayRef result = fn ArraySortedArrayUsingSelector( fn SetAllObjects( common ), @"compare:" )
return fn ArrayComponentsJoinedByString( result, @", " )
end fn = NULL
CFArrayRef nums
nums = @[@[@2,@5,@1,@3,@8,@9,@4,@6], @[@3,@5,@6,@2,@9,@8,@4], @[@1,@3,@7,@6,@9]]
printf @"%@", fn FindCommonElements( nums )
HandleEvents
- Output:
3, 6, 9
Go
package main
import "fmt"
func indexOf(l []int, n int) int {
for i := 0; i < len(l); i++ {
if l[i] == n {
return i
}
}
return -1
}
func common2(l1, l2 []int) []int {
// minimize number of lookups
c1, c2 := len(l1), len(l2)
shortest, longest := l1, l2
if c1 > c2 {
shortest, longest = l2, l1
}
longest2 := make([]int, len(longest))
copy(longest2, longest) // matching duplicates will be destructive
var res []int
for _, e := range shortest {
ix := indexOf(longest2, e)
if ix >= 0 {
res = append(res, e)
longest2 = append(longest2[:ix], longest2[ix+1:]...)
}
}
return res
}
func commonN(ll [][]int) []int {
n := len(ll)
if n == 0 {
return []int{}
}
if n == 1 {
return ll[0]
}
res := common2(ll[0], ll[1])
if n == 2 {
return res
}
for _, l := range ll[2:] {
res = common2(res, l)
}
return res
}
func main() {
lls := [][][]int{
{{2, 5, 1, 3, 8, 9, 4, 6}, {3, 5, 6, 2, 9, 8, 4}, {1, 3, 7, 6, 9}},
{{2, 2, 1, 3, 8, 9, 4, 6}, {3, 5, 6, 2, 2, 2, 4}, {2, 3, 7, 6, 2}},
}
for _, ll := range lls {
fmt.Println("Intersection of", ll, "is:")
fmt.Println(commonN(ll))
fmt.Println()
}
}
- Output:
Intersection of [[2 5 1 3 8 9 4 6] [3 5 6 2 9 8 4] [1 3 7 6 9]] is: [3 6 9] Intersection of [[2 2 1 3 8 9 4 6] [3 5 6 2 2 2 4] [2 3 7 6 2]] is: [3 6 2 2]
Haskell
import qualified Data.Set as Set
task :: Ord a => [[a]] -> [a]
task [] = []
task xs = Set.toAscList . foldl1 Set.intersection . map Set.fromList $ xs
main = print $ task [[2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9]]
- Output:
[3,6,9]
J
2 5 1 3 8 9 4 6([-.-.)3 5 6 2 9 8 4([-.-.)1 3 7 6 9
3 9 6
Or,
;([-.-.)&.>/2 5 1 3 8 9 4 6;3 5 6 2 9 8 4;1 3 7 6 9
3 9 6
Java
Since lists may contain duplicate items, this example has an additional test with lists containing duplicate items.
import java.util.List;
public final class CommonListElements {
public static void main(String[] args) {
List<List<List<Integer>>> tests = List.of(
List.of( List.of( 2, 5, 1, 3, 8, 9, 4, 6 ),
List.of( 3, 5, 6, 2, 9, 8, 4 ),
List.of( 1, 3, 7, 6, 9 ) ),
List.of( List.of( 2, 2, 1, 3, 8, 9, 4, 6 ),
List.of( 3, 5, 6, 2, 2, 2, 4 ),
List.of( 2, 3, 7, 6, 2 ) ) );
for ( List<List<Integer>> test : tests ) {
List<Integer> result = test.get(0).stream().filter(test.get(1)::contains).toList()
.stream().filter(test.get(2)::contains).toList();
System.out.println("intersection of " + test + " is: " + result);
}
}
}
- Output:
intersection of [[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]] is: [3, 9, 6] intersection of [[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]] is: [2, 2, 3, 6]
jq
Works with gojq, the Go implementation of jq
The following definition of `intersection` does not place any restrictions on the arrays whose intersection is sought. The helper function, `ios`, might be independently useful and so is defined as a top-level filter.
# If a and b are sorted lists, and if all the elements respectively of a and b are distinct,
# then [a,b] | ios will emit the stream of elements in the set-intersection of a and b.
def ios:
.[0] as $a | .[1] as $b
| if 0 == ($a|length) or 0 == ($b|length) then empty
elif $a[0] == $b[0] then $a[0], ([$a[1:], $b[1:]] | ios)
elif $a[0] < $b[0] then [$a[1:], $b] | ios
else [$a, $b[1:]] | ios
end ;
# input: an array of arbitrary JSON arrays
# output: their intersection as sets
def intersection:
def go:
if length == 1 then (.[0]|unique)
else [(.[0]|unique), (.[1:] | go)] | [ios]
end;
if length == 0 then []
elif any(.[]; length == 0) then []
else sort_by(length) | go
end;
# The task:
[[2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9]]
- Output:
[3,6,9]
K
{x^x^y}/(2 5 1 3 8 9 4 6;1 3 7 6 9;3 5 6 2 9 8 4)
3 9 6
Ksh
#!/bin/ksh
# Find the common list elements in an integer array nums[][]
# # Variables:
#
typeset -a nums=( (2 5 1 3 8 9 4 6) (3 5 6 2 9 8 4) (1 3 7 6 9) )
# # Functions:
#
# # Function _flatten(arr[][] arr[]) - flatten input matrix
#
function _flatten {
typeset _inarr ; nameref _inarr="$1"
typeset _outarr ; nameref _outarr="$2"
typeset _i ; integer _i
_oldIFS=$IFS ; IFS=\|
for ((_i=1; _i<${#_inarr[*]}; _i++)); do
_outarr[_i]=${_inarr[_i][*]}
done
IFS=$oldIFS
}
######
# main #
######
typeset -a flatarr output
_flatten nums flatarr
integer i j
for ((i=0; i<${#nums[0][*]}; i++)); do
integer cnt=0
for ((j=1; j<=${#flatarr[*]}; j++)); do
[[ ${nums[0][i]} == @(${flatarr[j]%\|}) ]] && (( cnt++ ))
done
(( cnt == 2 )) && output+=( ${nums[0][i]} )
done
print "( ${output[@]} )"
- Output:
( 3 9 6 )
Julia
julia> intersect([2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9])
3-element Array{Int64,1}:
3
9
6
Lambdatalk
{def intersection
{def intersection.r
{lambda {:a :b :c :d}
{if {A.empty? :a}
then :d
else {intersection.r {A.rest :a} :b :c
{if {and {> {A.in? {A.first :a} :b} -1}
{> {A.in? {A.first :a} :c} -1}}
then {A.addlast! {A.first :a} :d}
else :d} }}}}
{lambda {:a :b :c}
{A.sort! < {intersection.r :a :b :c {A.new}}} }}
-> intersection
{intersection
{A.new 2 5 1 3 8 9 4 6}
{A.new 3 5 6 2 9 8 4}
{A.new 1 3 7 6 9}
}
-> [3,6,9]
Mathematica /Wolfram Language
Intersection[{2, 5, 1, 3, 8, 9, 4, 6}, {3, 5, 6, 2, 9, 8, 4}, {1, 3, 7, 6, 9}]
- Output:
{3, 6, 9}
Maxima
common_elems(lst):=block(map(setify,lst),apply(intersection,%%),listify(%%))$
nums:[[2,5,1,3,8,9,4,6],[3,5,6,2,9,8,4],[1,3,7,6,9]]$
common_elems(nums);
- Output:
[3,6,9]
Nim
import algorithm, sequtils
proc commonElements(list: openArray[seq[int]]): seq[int] =
var list = sortedByIt(list, it.len) # Start with the shortest array.
for val in list[0].deduplicate(): # Check values only once.
block checkVal:
for i in 1..list.high:
if val notin list[i]:
break checkVal
result.add val
echo commonElements([@[2,5,1,3,8,9,4,6], @[3,5,6,2,9,8,4], @[1,3,7,6,9]])
- Output:
@[3, 6, 9]
Perl
@nums = ([2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9]);
map { print "$_ " if @nums == ++$c{$_} } @$_ for @nums;
- Output:
3 6 9
Phix
function intersection(sequence s) sequence res = {} if length(s) then for i=1 to length(s[1]) do integer candidate = s[1][i] bool bAdd = not find(candidate,res) for j=2 to length(s) do if not find(candidate,s[j]) then bAdd = false exit end if end for if bAdd then res &= candidate end if end for end if return res end function ?intersection({{2,5,1,3,8,9,4,6},{3,5,6,2,9,8,4},{1,3,7,6,9}}) ?intersection({{2,2,1,3,8,9,4,6},{3,5,6,2,2,2,4},{2,3,7,6,2}})
Note that a (slightly more flexible) intersection() function is also defined in sets.e, so you could just include that instead, and use it the same way.
- Output:
{3,9,6} {2,3,6}
Python
Without Duplicates
"""Find distinct common list elements using set.intersection."""
def common_list_elements(*lists):
return list(set.intersection(*(set(list_) for list_ in lists)))
if __name__ == "__main__":
test_cases = [
([2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]),
([2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]),
]
for case in test_cases:
result = common_list_elements(*case)
print(f"Intersection of {case} is {result}")
- Output:
intersection of ([2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]) is [9, 3, 6] intersection of ([2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]) is [2, 3, 6]
With Duplicates
"""Find common list elements using collections.Counter (multiset)."""
from collections import Counter
from functools import reduce
from itertools import chain
def common_list_elements(*lists):
counts = (Counter(list_) for list_ in lists)
intersection = reduce(lambda x, y: x & y, counts)
return list(chain.from_iterable([elem] * cnt for elem, cnt in intersection.items()))
if __name__ == "__main__":
test_cases = [
([2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]),
([2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]),
]
for case in test_cases:
result = common_list_elements(*case)
print(f"Intersection of {case} is {result}")
- Output:
intersection of ([2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]) is [9, 3, 6] intersection of ([2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]) is [2, 2, 3, 6]
Quackery
[ behead sort swap witheach
[ sort [] temp put
[ over [] !=
over [] != and while
over 0 peek
over 0 peek = iff
[ behead temp take
swap join temp put
swap behead drop ] again
over 0 peek
over 0 peek < if swap
behead drop again ]
2drop temp take ] ] is common ( [ [ --> [ )
' [ [ 2 5 1 3 8 9 4 6 ] [ 3 5 6 2 9 8 4 ] [ 1 3 7 6 9 ] ] common echo
- Output:
[ 3 6 9 ]
Raku
put [∩] [2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9,3];
- Output:
6 9 3
REXX
This REXX version properly handles the case of duplicate entries in a list (which shouldn't happen in a true list).
/*REXX program finds and displays the common list elements from a collection of sets. */
parse arg a /*obtain optional arguments from the CL*/
if a='' | a="," then a= '[2,5,1,3,8,9,4,6] [3,5,6,2,9,8,4] [1,3,7,6,9]' /*defaults.*/
#= words(a) /*the number of sets that are specified*/
do j=1 for # /*process each set in a list of sets.*/
@.j= translate( word(a, j), ,'],[') /*extract a " from " " " " */
end /*j*/
$= /*the list of common elements (so far).*/
do k=1 for #-1 /*use the last set as the base compare.*/
do c=1 for words(@.#); x= word(@.#, c) /*obtain an element from a set. */
do f=1 for #-1 /*verify that the element is in the set*/
if wordpos(x, @.f)==0 then iterate c /*Is in the set? No, then skip element*/
end /*f*/
if wordpos(x, $)==0 then $= $ x /*Not already in the set? Add common. */
end /*c*/
end /*k*/
/*stick a fork in it, we're all done. */
say 'the list of common elements in all sets: ' "["translate(space($), ',', " ")']'
- output when using the default inputs:
the list of common elements in all sets: [3,6,9]
Ring
nums = [[2,5,1,3,8,9,4,6],[3,5,6,2,9,8,4],[1,3,7,6,9]]
sumNums = []
result = []
for n = 1 to len(nums)
for m = 1 to len(nums[n])
add(sumNums,nums[n][m])
next
next
sumNums = sort(sumNums)
for n = len(sumNums) to 2 step -1
if sumNums[n] = sumNums[n-1]
del(sumNums,n)
ok
next
for n = 1 to len(sumNums)
flag = list(len(nums))
for m = 1 to len(nums)
flag[m] = 1
ind = find(nums[m],sumNums[n])
if ind < 1
flag[m] = 0
ok
next
flagn = 1
for p = 1 to len(nums)
if flag[p] = 1
flagn = 1
else
flagn = 0
exit
ok
next
if flagn = 1
add(result,sumNums[n])
ok
next
see "common list elements are: "
showArray(result)
func showArray(array)
txt = ""
see "["
for n = 1 to len(array)
txt = txt + array[n] + ","
next
txt = left(txt,len(txt)-1)
txt = txt + "]"
see txt
- Output:
common list elements are: [3,6,9]
RPL
Can handle duplicates.
« SWAP LIST→ → n « 'n' DECR DUP 3 + ROLL - 2 + ROLL DROP n →LIST » » 'POPL' STO @ ( {list} idx_item_to_remove → {list} ) « IF OVER SIZE OVER SIZE < THEN SWAP END 0 → a j « { } SWAP WHILE 'j' INCR a SIZE ≤ REPEAT a j GET IF DUP2 POS THEN LASTARG ROT SWAP POPL ROT ROT + SWAP ELSE DROP END END DROP » » 'INTER' STO
{ 2 5 1 3 8 9 4 6 } { 3 5 6 2 9 8 4 } { 1 3 7 6 9 } INTER INTER { 2 2 1 3 8 9 4 6 } { 3 5 6 2 2 2 4 } { 2 3 7 6 2 } INTER INTER
- Output:
2: { 3 6 9 } 1: { 3 6 2 2 }
Ruby
nums = [2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9]
p nums.inject(&:intersection) # or nums.inject(:&)
- Output:
[3, 9, 6]
Rust
use std::collections::HashSet;
use std::hash::Hash;
fn intersections<T>(sets: &[HashSet<T>]) -> HashSet<T>
where
T: Clone + Eq + Hash,
{
sets.iter()
.enumerate()
.min_by_key(|&(_, s)| s.len())
.map(|(smallest_set_index, _)| {
let (other_sets_left, [smallest_set, other_sets_right @ ..]) =
sets.split_at(smallest_set_index)
else {
unreachable!()
};
let other_sets = || other_sets_left.iter().chain(other_sets_right);
smallest_set
.iter()
.filter(|item| other_sets().all(|o| o.contains(item)))
.cloned()
.collect()
})
.unwrap_or_default()
}
fn intersection_all<T>(a: &Vec<Vec<T>>) -> Vec<T> where T: Copy + Eq + Hash + Ord {
let hashsets = &a
.iter()
.map(|a| HashSet::from_iter(a.iter().cloned()))
.collect::<Vec<HashSet<T>>>()[..];
let mut ret: Vec<T> = intersections(hashsets).iter().map(|x| *x).collect();
ret.sort();
return ret;
}
fn main() {
let a = [0, 1, 2, 3, 4, 5].to_vec();
let b = [4, 2, 0, 3, 4].to_vec();
let c = [0, 1, 2, 3, 4, 8, 9, 5].to_vec();
println!("{:?}", intersection_all(&[a, b, c].to_vec()));
let astring = ["the", "cat", "in", "the", "hat",].to_vec();
let bstring = ["the", "wind", "in", "the", "grass",].to_vec();
let cstring = ["the", "ship", "takes", "any", "port", "in", "a", "storm"].to_vec();
println!("{:?}", intersection_all(&[astring, bstring, cstring].to_vec()));
}
- Output:
[0, 2, 3, 4] ["in", "the"]
V (Vlang)
fn index_of(l []int, n int) int {
for i in 0..l.len {
if l[i] == n {return i}
}
return -1
}
fn common2(l1 []int, l2 []int) []int {
// minimize number of lookups
c1, c2 := l1.len, l2.len
mut shortest, mut longest := l1.clone(), l2.clone()
if c1 > c2 {shortest, longest = l2.clone(), l1.clone()}
mut longest2 := longest.clone()
mut res := []int{}
for e in shortest {
ix := index_of(longest2, e)
if ix >= 0 {
res << e
longest2 << longest2[ix+1..]
}
}
return res
}
fn common_n(ll [][]int) []int {
n := ll.len
if n == 0 {return []int{}}
if n == 1 {return ll[0]}
mut res := common2(ll[0], ll[1])
if n == 2 {return res}
for l in ll[2..] {
res = common2(res, l)
}
return res
}
fn main() {
lls := [
[[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]],
[[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]],
]
for ll in lls {
println("Intersection of $ll is:")
println(common_n(ll))
println("")
}
}
- Output:
Intersection of [[2, 5, 1, 3, 8, 9, 4, 6] [3, 5, 6, 2, 9, 8, 4] [1, 3, 7, 6, 9]] is: [3, 6, 9] Intersection of [[2 2 1 3 8 9 4 6] [3 5 6 2 2 2 4] [2, 3, 7, 6, 2]] is: [3, 6, 2, 2]
Alternative:
fn main()
{
lls := [
[[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]],
[[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]],
]
for ll in lls {
println("Intersection of $ll is:")
println(common_list_elements(ll))
println("")
}
}
fn common_list_elements(md_arr [][]int) []int {
mut counter := map[int]int{}
mut output := []int{}
for sd_arr in md_arr {
for value in sd_arr {
if counter[value] == counter[value] {counter[value] = counter[value] + 1} else { 1 } {
if counter[value] >= md_arr.len && output.any(it == value) == false {output << value}
}
}
}
return output
}
- Output:
Intersection of [[2, 5, 1, 3, 8, 9, 4, 6] [3, 5, 6, 2, 9, 8, 4] [1, 3, 7, 6, 9]] is: [3, 6, 9] Intersection of [[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]] is: [2, 3, 6]
Wren
As we're dealing here with lists rather than sets, some guidance is needed on how to deal with duplicates in each list in the general case. A drastic solution would be to remove all duplicates from the result. Instead, the following matches duplicates - so if List A contains 2 'a's and List B contains 3 'a's, there would be 2 'a's in the result.
import "./seq" for Lst
var common2 = Fn.new { |l1, l2|
// minimize number of lookups
var c1 = l1.count
var c2 = l2.count
var shortest = (c1 < c2) ? l1 : l2
var longest = (l1 == shortest) ? l2 : l1
longest = longest.toList // matching duplicates will be destructive
var res = []
for (e in shortest) {
var ix = Lst.indexOf(longest, e)
if (ix >= 0) {
res.add(e)
longest.removeAt(ix)
}
}
return res
}
var commonN = Fn.new { |ll|
var n = ll.count
if (n == 0) return ll
if (n == 1) return ll[0]
var first2 = common2.call(ll[0], ll[1])
if (n == 2) return first2
return ll.skip(2).reduce(first2) { |acc, l| common2.call(acc, l) }
}
var lls = [
[[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]],
[[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]]
]
for (ll in lls) {
System.print("Intersection of %(ll) is:")
System.print(commonN.call(ll))
System.print()
}
- Output:
Intersection of [[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]] is: [3, 6, 9] Intersection of [[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]] is: [2, 3, 6, 2]
Since the above was written, we can also now offer a library based solution.
import "./seq" for Lst
var lls = [
[[2, 5, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 9, 8, 4], [1, 3, 7, 6, 9]],
[[2, 2, 1, 3, 8, 9, 4, 6], [3, 5, 6, 2, 2, 2, 4], [2, 3, 7, 6, 2]]
]
for (ll in lls) {
System.print(Lst.intersect(ll[0], Lst.intersect(ll[1], ll[2])))
}
- Output:
[3, 9, 6] [2, 2, 3, 6]
XPL0
A 32-bit integer is used to specify a set of values 0..31. The [-1] terminator helps determine the number of lists.
int IntSize, Nums, Sets, Ans, N, ListSize, Set, I;
[IntSize:= @Nums - @IntSize; \number of bytes in an integer
Nums:= [[2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9], [-1]];
Sets:= 0; \find the number of lists = number of Sets
while Nums(Sets, 0) > 0 do Sets:= Sets+1;
Ans:= -1;
for N:= 0 to Sets-1 do
[ListSize:= (Nums(N+1) - Nums(N)) / IntSize;
Set:= 0;
for I:= 0 to ListSize-1 do \Set = union (or) of list elements
Set:= Set or 1<<Nums(N, I);
Ans:= Ans & Set; \Answer is intersection (&) of Sets
];
I:= 0;
while Ans do \show common list elements
[if Ans & 1 then
[IntOut(0, I); ChOut(0, ^ )];
Ans:= Ans>>1;
I:= I+1;
];
]
- Output:
3 6 9
- Draft Programming Tasks
- 11l
- Action!
- Action! Tool Kit
- Ada
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BQN
- C++
- CLU
- Excel
- Delphi
- SysUtils,StdCtrls
- DuckDB
- EasyLang
- F Sharp
- Factor
- FreeBASIC
- FutureBasic
- Go
- Haskell
- J
- Java
- Jq
- K
- Ksh
- Julia
- Lambdatalk
- Mathematica
- Wolfram Language
- Maxima
- Nim
- Perl
- Phix
- Python
- Quackery
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- V (Vlang)
- Wren
- Wren-seq
- XPL0