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 contains most consonants
- Find words which contains more than 3 vowels
- Find words which first and last three letters are equals
- Find words which odd letters are consonants and even letters are vowels or vice_versa
- 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
APL
APL has the built-in intersection function ∩
<lang APL> ∩/ (2 5 1 3 8 9 4 6) (3 5 6 2 9 8 4) (1 3 7 9 6)
3 9 6 </lang>
AutoHotkey
<lang 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
} </lang> Examples:<lang AutoHotkey>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</lang>
- Output:
[3, 6, 9]
AWK
<lang 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)
} </lang>
- Output:
[2,5,1,3,8,9,4,6],[3,5,6,2,9,8,4],[1,3,7,6,9] : 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)
<lang lisp>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 )
)</lang>
and also assuming the following generic bindings in Name Manager: <lang lisp>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() ) )
)</lang>
- 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 |
F#
Of course it is possible to use sets but I thought the idea was not to? <lang fsharp> // 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)));; </lang>
- Output:
[3; 9; 6]
Factor
Note: in older versions of Factor, intersect-all
was called intersection
.
<lang factor>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 .</lang>
- Output:
{ 3 6 9 }
Go
<lang 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() }
}</lang>
- 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
<lang 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]]</lang>
- Output:
[3,6,9]
Julia
<lang 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
</lang>
Perl
<lang 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;</lang>
- 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
<lang python>"""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}")
</lang>
- 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
<lang python>"""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}")
</lang>
- 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]
Raku
<lang perl6>put [∩] [2,5,1,3,8,9,4,6], [3,5,6,2,9,8,4], [1,3,7,6,9,3];</lang>
- 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). <lang rexx>/*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($), ',', " ")']'</lang>
- output when using the default inputs:
the list of common elements in all sets: [3,6,9]
Ring
<lang 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
</lang>
- Output:
common list elements are: [3,6,9]
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. <lang ecmascript>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()
}</lang>
- 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]