Jump to content

Common list elements

From Rosetta Code
Common list elements is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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]


Other tasks related to string operations:
Metrics
Counting
Remove/replace
Anagrams/Derangements/shuffling
Find/Search/Determine
Formatting
Song lyrics/poems/Mad Libs/phrases
Tokenize
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

Works with: Delphi version 6.0


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

Works with: DuckDB version V1.0

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.

Works with: Factor version 0.99 2021-02-05
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

Translation of: Wren
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: 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

Works with: ngn/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.

Works with: HP version 48
« 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)

Translation of: Go
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

Library: Wren-seq

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 
Cookies help us deliver our services. By using our services, you agree to our use of cookies.