# Lists' intersection keeping elements' order

I could use the function Intersection, but it returns a sorted list. That's why I have to do my own, but it looks too big. I hope it could be done shorter.

lists = {{1, 2, 3, 4, 5}, {1, 2, 3, 4}, {2, 3, 4, 5}};
Fold[ Function[ {a, b},
Select[b, MemberQ[a, #] &]
], lists // First, lists // Rest]

• what should be result of Intersect[{{1,2},{2,1}}] ?
– ralu
Commented Apr 15, 2011 at 9:44
• @ralu, in my case such incoming data is impossible. In my case the same pair of elements can't go in reversed order in another list - always in the same order. For example, possible {5,7,6,3},{5,6,1,3} but not {5,7,6,3},{5,6,7,3}. Commented Apr 17, 2011 at 10:55

This function deletes from the first list all the elements not contained in the intersection, thus returning what you want:

f[l_List]:= DeleteCases[First@l, Except[Alternatives @@ (Intersection @@ l)]]

f[{{1, 2, 3, 4, 5}, {1, 2, 3, 4}, {2, 3, 4, 5}}]
->{2,3,4}

f[{{5, 7, 6, 3}, {5, 6, 1, 3}}]
->{5,6,3}


Why use a reverse approach? Just do it directly!

Cases[First[list], Alternatives @@ Intersection @@ list]


If speed mattered, one could define a temporary "tester" function inside a Module to use in place of MemberQ

Module[ {f},
(f[#] = True)& /@ (Intersection @@ list);
Select[First[list], f]
]


This is still fairly short.

Most efficient and simple way for this is to sort each list before applying such algorithm. In this case you do not need to check if each number is memeber of other list but you just pick first number and compare whit other elements from beginning.

This is reason that Mathematica return sorted list. In case that each list is sorted complexity is O(N) where N is total number of all elements.

• Sure, but I'm gonna use this code 20-50 times in my life, for 5-10 lists each of 10-30 elements. So here no need of speed, here need of small size of code to read it next time faster. Commented Apr 15, 2011 at 8:09