How do I obtain an intersection of two or more list of lists conditioned on the first element of each sub-list?

Question

Given two lists like

list1 = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};
list2 = {{2, 6}, {3, 9}, {4, 12}, {5, 15}};

I would like to produce an output like

listout = {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}

Community · Accepted Answer · 2017-04-13 12:55:36Z

Good question. Second try.

Sow & Reap:

f1[a_List, b_List] := 
   Reap[Sow[#2, #] & @@@ a ~Join~ b, a[[All, 1]] ⋂ b[[All, 1]], List][[2, All, 1]]

Pick:

f2[a_List, b_List] :=
 With[{aa = a[[All, 1]], bb = b[[All, 1]]},
   {#[[1, 1]], #[[All, 2]]} & /@
      Pick[a ~Join~ b, aa ~Join~ bb, Alternatives @@ (aa ⋂ bb)] ~GatherBy~ First
 ]

Edit: Here is another method using GatherBy. While this method did not come to mind when I first wrote this answer I have used related methods for some time. It works by preconditioning GatherBy so that we collect the expressions we want at the beginning of the results and then discarding the rest. This is the same principle I used for How to Delete Elements from List1 appearing in List2? and more recently Complement on pre-sorted lists, and which jVincent used for Counting the population of integers.

f3[a_List, b_List] := 
  With[{pre = List /@ ( a[[All, 1]] ⋂ b[[All, 1]] )},
    {pre[[All, 1]], GatherBy[Join[pre, a, b], First][[;; Length@pre, 2 ;;, 2]]}\[Transpose]
  ]

At the expense of greater code length this can be made faster by using Szabolcs's inversion method with GatherBy:

f4[a_List, b_List] :=
 Module[{pre, first, all, n, a1, b1},
   {a1, b1} = {a[[All, 1]], b[[All, 1]]};
   n = Length[pre = a1 ⋂ b1];
   first = Join[pre, a1, b1];
   all = Join[a, b];
   {pre, Map[all[[#, 2]] &, 
      GatherBy[Range@Length@first, first[[#]] &][[;; n, 2 ;;]] - n]}\[Transpose]
 ]

Test:

list1 = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};
list2 = {{2, 6}, {3, 9}, {4, 12}, {5, 15}, {5, 7}};

f1[list1, list2]

{{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}

I included {5, 7} in list2 to show that this is finding the intersection of the two lists and not merely repeats within a single list.

For those of us who cannot read infix: f2[a_, b_] := ({#1[[1, 1]], #1[[All, 2]]} & ) /@ GatherBy[ Cases[Join[a, b], {Alternatives @@ Intersection[a[[All, 1]], b[[All, 1]]], _}], First] — Mike Honeychurch, Commented Dec 17, 2012 at 6:56
Looks fine to me. Would be interested to know how Apply Alternative compares with the MemberQ test for larger lists. I normally use Alternative but forgot all about it when I wrote my answer — Mike Honeychurch, Commented Dec 17, 2012 at 6:57
@Mike Alternatives test quite a bit faster than MemberQ for me. For pure speed this seems best of what I've tried: Pick[#, First /@ #, Alternatives @@ inter] & @ Join[a, b] where inter is the first elements intersection. — Mr.Wizard, Commented Dec 17, 2012 at 7:10
Yes Pick will generally provide a much faster solution than e.g. Cases/Select if you can develop a Pick method. — Mike Honeychurch, Commented Dec 17, 2012 at 7:35

Mr.Wizard · Accepted Answer · 2012-12-17 07:55:31Z

13

this works for the given example:

ReplaceList[{list1, list2}, {{___, {a_, b_}, ___}, {___, {a_, c_}, ___}} :> {a, {b, c}}]

(* {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}} *)

edited Dec 17, 2012 at 7:55

Mr.Wizard

273k34 gold badges595 silver badges1.4k bronze badges

answered Dec 17, 2012 at 7:38

kptnw

1,4168 silver badges16 bronze badges

2

$\begingroup$ Very clever! However, this runs into problems if there are duplicates (in terms of first element) internally in either list. It is also rather slow on longer lists. Enthusiastic +1 nevertheless! $\endgroup$
– Mr.Wizard
Commented Dec 17, 2012 at 7:46
2

$\begingroup$ An additional note: make sure you use RuleDelayed (:>) when working with named patterns on the right-hand side. This correctly localizes the symbols. I made this edit for you; I hope you don't mind. $\endgroup$
– Mr.Wizard
Commented Dec 17, 2012 at 7:56
$\begingroup$ @Mr.Wizard Thanks for your vote, your editing, and many of your wonderful answers I learn and love :) $\endgroup$
– kptnw
Commented Dec 17, 2012 at 10:51

Add a comment |

kglr · Accepted Answer · 2012-12-17 10:34:23Z

Update 3: A generalization for any number of lists and any column as the key:

 ClearAll[combineBy];
 combineBy[lists : __List, col_Integer] /; (col <= Min[Length /@ # & /@ {lists}]) := 
  With[{intNodes =  Alternatives @@ Intersection @@ (#[[col]] & /@ # & /@ {lists}),
  joined = GatherBy[Join[lists], #[[col]] &],
  othercols = DeleteCases[Range[Min[Length /@ # & /@ {lists}]], col]},
  {#[[1, col]], Join @@ #[[All, othercols]]} & /@
     Pick[joined, ! FreeQ[#[[1, col]], intNodes] & /@ joined]]

OP's example:

  list1 = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};
  list2 = {{2, 6}, {3, 9}, {4, 12}, {5, 15}, {5, 7}};
  combineBy[list1, list2, 1]
  (* {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}} *)
  combineBy[list1, list2, 2]
  (* {{9, {3, 3}}} *)

More examples:

  list3 = Table[RandomSample[Range[7], 3], {3}];
  list4 = Table[RandomSample[Range[7], 3], {4}];
  list5 = Table[RandomSample[Range[7], 3], {6}];

  Prepend[Prepend[{SpanFromAbove, SpanFromAbove,  #, 
   Column[combineBy[list4, list5, #]]} & /@ {2, 3},
   {Column@list4, Column@list5, 1, Column[combineBy[list4, list5, 1]]}],
   {"list4", "list5", "key column", "result"}] //
   Grid[#, Alignment -> {Center, Center}, Dividers -> All] &

enter image description here

  Prepend[Prepend[{SpanFromAbove, SpanFromAbove, #, 
   Column[combineBy[list3, list4, #]]} & /@ {2, 3},
   {Column@list3, Column@list4, 1, Column[combineBy[list3, list4, 1]]}],
   {"list3", "list4", "key column", "result"}] //
   Grid[#, Alignment -> {Center, Center}, Dividers -> All] &

enter image description here

  Prepend[Prepend[{SpanFromAbove, SpanFromAbove,  #, 
   Column[combineBy[list3, list5, #]]} & /@ {2, 3},
   {Column@list3, Column@list5, 1,  Column[combineBy[list3, list5, 1]]}],
   {"list3", "list5", "key column", "result"}] //
   Grid[#, Alignment -> {Center, Center}, Dividers -> All] &

enter image description here

  Prepend[Prepend[{SpanFromAbove, SpanFromAbove, SpanFromAbove,  #, 
     Column[combineBy[list3, list4, list5, #]]} & /@ {2, 3},
    {Column@list3, Column@list4, Column@list5, 1,
      Column[combineBy[list3, list4, list5, 1]]}],
    {"list3", "list4", "list5", "key column", "result"}] //
   Grid[#, Alignment -> {Center, Center}, Dividers -> All] &

enter image description here

  ClearAll[combine];
  combine[list1_List, list2_List] := 
  With[{intNodes = Intersection[First /@ list1, First /@ list2], 
    joined =  GatherBy[Join[list1, list2], First]},
    {First[First@#],  Last[#]} & /@ (Transpose /@ 
    Select[joined, MemberQ[intNodes, #[[1, 1]]] &])]

 combine[list1, list2]
 (* {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}} *)
 combine[list1, {{2, 6}, {3, 9}, {4, 12}, {5, 15}, {5, 7}}]
 (* {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}} *)

(Updated with correction thanks to @Mr.W's comment: the second argument of Select is changed from Length[#]>2& in the original post to the correct version that accounts for the intersection of the first columns of the two lists.)

Update 2: Using Pick instead of Select:

ClearAll[combine2];
combine2[list1_List, list2_List] := 
 With[{intNodes = Intersection[First /@ list1, First /@ list2], 
   joined =  GatherBy[Join[list1, list2], First]}, 
 {#[[1, 1]], #[[-1]]} & /@ 
  (Transpose /@ Pick[joined, MemberQ[intNodes, #[[1, 1]]] & /@ joined])]

Funny, I was just trying Pick myself. See the comments below my answer. Great minds and all that. — Mr.Wizard, Commented Dec 17, 2012 at 7:12
@Mr.W, of the triplets (Cases, Select,Pick), Pick is almost always the first that I try ... and it rarely disappoints. — kglr, Commented Dec 17, 2012 at 7:38

Murta · Accepted Answer · 2012-12-17 11:33:10Z

7

I like this one:

{#[[1,1]],#[[All,2]]}&/@Select[GatherBy[list1~Join~list2,First],Length[#]>1&]

(*{{2,{4,6}},{3,{9,9}},{4,{16,12}}}*)

answered Dec 17, 2012 at 11:33

Murta

26.4k6 gold badges77 silver badges168 bronze badges

Add a comment |

Nasser · Accepted Answer · 2012-12-17 14:07:19Z

7

a = Join[list1, list2]
n = Length[list1];
{a[[#, 1]], {a[[#, 2]], a[[# + n - 1, 2]]}} & /@ Range[2, n]

![Mathematica graphics](https://i.sstatic.net/FXKvd.png)

Explanation: Use linear indexing. We have 2 matrices as input. list1 and list2. Each is an n by 2 size matrix. Joining them results in one 2n by 2 matrix called a. This diagram explains the algorithm enter image description here

edited Dec 17, 2012 at 14:07

answered Dec 17, 2012 at 7:12

Nasser

150k12 gold badges161 silver badges374 bronze badges

$\begingroup$ Am I correct in observing that this only works if the two lists have a common ordered subset, e.g. {2, 3, 4}? $\endgroup$
– Andrew Cheong
Commented Aug 25, 2013 at 3:34

Add a comment |

Mike Honeychurch · Accepted Answer · 2012-12-17 08:06:42Z

6

Edit 1

processList[list1_, list2_] := Module[{intersection, tmp1, tmp2},

 (* find the intersection of the all the first elements *)
  intersection = Intersection[list1[[All, 1]], list2[[All, 1]]];

 (* now find cases in each list in which the first element is one of the intersecting   
  elements *)
  tmp1 = Cases[list1, {x_ /; MemberQ[intersection, x], __}];
  tmp2 = Cases[list2, {x_ /; MemberQ[intersection, x], __}];

  (* now gather all sub-lists based on the first element and map them to give the   
  desired output *)
  {#[[1, 1]], ##[[All, 2]]} & /@ GatherBy[Join[tmp1, tmp2], First]
  ]

test:

processList[list1, {{2, 6}, {3, 9}, {4, 12}, {5, 15}, {5, 7}}]
(* {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}} *)

Edit 2

Since we're onto Pick methods :) ...this seems relatively concise. Two steps from above and then pick out the elements for output.

processList2[list1_, list2_] := Module[{intersection, tmp},

  intersection = Intersection[list1[[All, 1]], list2[[All, 1]]];
  tmp = {#[[1, 1]], ##[[All, 2]]} & /@ GatherBy[Join[list1, list2], First];
  Pick[tmp, tmp[[All, 1]] /. Thread[Rule[intersection, True]]]
  ]

list2 = {{2, 6}, {3, 9}, {4, 12}, {5, 15}, {5, 7}};
processList2[list1, list2]
(* {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}  *)

For all of these Pick methods I'm not sure how efficient creating the stencil can be for this particular problem. If the stencil is efficiently created then Pick is a fast way of picking out elements from lists.

edited Dec 17, 2012 at 8:06

answered Dec 17, 2012 at 6:04

Mike Honeychurch

37.8k3 gold badges87 silver badges161 bronze badges

$\begingroup$ How does this find an intersection of the two lists? $\endgroup$
– Mr.Wizard
Commented Dec 17, 2012 at 6:08
$\begingroup$ Re: Edit, that looks like a more intelligent approach than the one I just posted. I hope you don't mind if I borrow from it. :-) $\endgroup$
– Mr.Wizard
Commented Dec 17, 2012 at 6:21
$\begingroup$ @Mr.Wizard not sure how intelligent it is, or efficient. Just a stepwise approach. :) $\endgroup$
– Mike Honeychurch
Commented Dec 17, 2012 at 6:24
$\begingroup$ Please take a look at my answer now and tell me if you see anything wrong. $\endgroup$
– Mr.Wizard
Commented Dec 17, 2012 at 6:43
$\begingroup$ Perhaps I should insist on your removing infix notation before looking at it :) $\endgroup$
– Mike Honeychurch
Commented Dec 17, 2012 at 6:58

Add a comment |

Rolf Mertig · Accepted Answer · 2012-12-18 12:16:19Z

3

Just for fun, a rule-based approach:

list2/.{{i_Integer/;!MemberQ[list1[[All,1]],i],x_}:>Sequence[],{i_Integer,x_}:>{i,{i/.(Rule@@@list1),x}}}

answered Dec 18, 2012 at 12:16

Rolf Mertig

17.4k1 gold badge46 silver badges78 bronze badges

Add a comment |

eldo · Accepted Answer · 2023-11-21 10:09:24Z

2

Using Association - related functions (not yet available in 2012)

a = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};
b = {{2, 6}, {3, 9}, {4, 12}, {5, 15}};

Cases[{_, {_, __}}] @
 KeyValueMap[List] @ Merge[# &] @ MapApply[Rule] @ Join[a, b]

{{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}

answered Nov 21, 2023 at 10:09

eldo

83.1k6 gold badges72 silver badges202 bronze badges

Add a comment |

kglr · Accepted Answer · 2023-11-21 10:47:54Z

GroupBy

WolframLanguageData["GroupBy",
  {"VersionIntroduced",  "DateIntroduced"}]

a = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};
b = {{2, 6}, {3, 9}, {4, 12}, {5, 15}};

MapApply[List] @
Normal @ 
Select[Length @ # > 1 &] @ 
GroupBy[Join[a, b], First -> Last]

{{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}

Map[{#[[1, 1]], Flatten @ #[[All, 2 ;;]]} &] @
Values @ 
Select[Length@# > 1 &] @ 
GroupBy[Join[a, b], First]

{{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}

WolframLanguageData["WolframLanguageData", 
  {"VersionIntroduced",  "DateIntroduced"}]

eldo · Accepted Answer · 2024-06-01 00:14:09Z

2

a = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};

b = {{2, 6}, {3, 9}, {4, 12}, {5, 15}};

Cases[x : {_, __} :> {x[[1, 1]], x[[All, -1]]}] @ GatherBy[Join[a, b], First]

{{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}

answered Jun 1 at 0:14

eldo

83.1k6 gold badges72 silver badges202 bronze badges

Add a comment |

ubpdqn · Accepted Answer · 2024-06-01 00:56:17Z

2

Using Association, KeyIntersection, Merge:

list1 = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};
list2 = {{2, 6}, {3, 9}, {4, 12}, {5, 15}};


a1 = Association[#1 -> #2 & @@@ list1];
a2 = Association[#1 -> #2 & @@@ list2];
List @@@ Normal[Merge[KeyIntersection[{a1, a2}], Identity]]

-> {{2, {4, 6}}, {3, {9, 9}}, {4, {16, 12}}}

answered Jun 1 at 0:56

ubpdqn

64.8k3 gold badges65 silver badges154 bronze badges

Add a comment |

user1066 · Accepted Answer · 2023-11-21 20:33:45Z

1

Cases[KeyValueMap[List]@GroupBy[Join[list1,list2],First->Last],{a_,{b_,c__}}->{a,{b,c}}]

(* {{2,{4,6}},{3,{9,9}},{4,{16,12}}} *)

list1x = {{1, 1}, {2, 4}, {3, 9}, {4, 16}};
list2x = {{2, 6}, {3, 9}, {4, 12}, {5, 15},{2,100},{2,2},{2,1}};

Cases[KeyValueMap[List]@GroupBy[Join[list1x,list2x],First->Last],{a_,{b_,c__}}->{a,{b,c}}]

(* {{2,{4,6,100,2,1}},{3,{9,9}},{4,{16,12}}} *)

answered Nov 21, 2023 at 20:33

user1066

22.7k3 gold badges36 silver badges59 bronze badges

Add a comment |

martin · Accepted Answer · 2024-06-01 03:53:47Z

1

Select[Thread@{
(First/@#&/@#)[[All,1]], Last/@#&/@#}&@
  SplitBy[SortBy[
    Join[list1,list2],
  First],First],
Length@#[[2]]>1&]

answered Jun 1 at 3:53

martin

8,9204 gold badges27 silver badges71 bronze badges

Add a comment |

Stack Exchange Network

How do I obtain an intersection of two or more list of lists conditioned on the first element of each sub-list?

13 Answers 13

GroupBy

Your Answer

Not the answer you're looking for? Browse other questions tagged
list-manipulation
or ask your own question.

Linked

Hot Network Questions

13 Answers 13

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged list-manipulation or ask your own question.

Linked

Related

Not the answer you're looking for? Browse other questions tagged
list-manipulation
or ask your own question.