# Truncating a list once all members of a set have appeared?

Consider if you would the case where we have some list of elements:

list0 = {54, 4, 7, 9, 3, 54, 4, 20, 2, 456, 2, 3};


And we have some target list:

targetList = {2, 3, 4, 7};


We'd like to scan from left to right through list0 and chop off an RHS tail at the moment all elements in targetList have appeared. With the example given we would have:

list0chopped = {54, 4, 7, 9, 3, 54, 4, 20, 2};


As an output.

Is there a simple way to do this?

I propose:

truncate[a_List, b_List] :=
a ~Take~ Max @ Lookup[PositionIndex[a][[All, 1]], b, 0]


For maximum performance replace PositionIndex with cleanPosIdx from Why is the new PositionIndex horribly slow?

I'll add comparative timings later if I get the chance.

• Very nice. I like Lookup[....,0] to get rid of MissingKey.+1 – Algohi Dec 24 '14 at 20:54

Maybe this would help:

list0[[;; Max[First /@ (Position[list0, #] & /@ targetList)]]]

(*{54, 4, 7, 9, 3, 54, 4, 20, 2}*)


In case targetList contains elements not in list0 then: (*Thanks to Chris Degnen*)

 list0[[;; Max[First /@ (Position[list0, #] & /@ Intersection[list0, targetList])]]]

• +1, also with If[Intersection[list0, targetList] == Sort@targetList, ...] – Chris Degnen Dec 24 '14 at 16:07
• I have an aversion to mapping Position across a list; see: (25591). You can avoid that by using PositionIndex as I did in my answer. However since since my answer is otherwise very similar +1. – Mr.Wizard Dec 24 '14 at 20:16

This s/b snappy for lists of any type:

f=#1[[;; With[{l = Length@#2},
Max[Sort[Partition[Ordering[Join[#2, #1]], 2, 1]][[;; l, 2]]] - l]]] &;

f[list0, targetList]


{54, 4, 7, 9, 3, 54, 4, 20, 2}

f1 = Module[{i = Length @ #2}, While[Not[ContainsAll[#[[;; i++]], #2]]]; #[[;; i - 1]]]&;

f1[list0, targetList]


{54, 4, 7, 9, 3, 54, 4, 20, 2}

f2 = Replace[#, {x__,y___} /; ContainsAll[{x}, #2] :> {x}]&
f2[list0, targetList]


{54, 4, 7, 9, 3, 54, 4, 20, 2}

If the list consists of positive integers smaller than some reasonable maximum, then the following function should be pretty fast:

trunc[a_, b_] := Module[{c = ConstantArray[0, Max[a]]},
c[[Reverse @ a]] = Reverse @ Range @ Length @ a;
Replace[
MinMax[c[[b]]],
{
{0, _} -> a,
{_, i_} :> a[[;;i]]
}
]
]


Here is trunc applied to the OP example:

trunc[
{54, 4, 7, 9, 3, 54, 4, 20, 2, 456, 2, 3},
{2, 3, 4, 7}
]


{54, 4, 7, 9, 3, 54, 4, 20, 2}

And, here trunc is compared to some of the other answers:

a = RandomInteger[{1, 10^4}, 10^5];
b = RandomSample[Range[10^4], 100];

r1 = trunc[a, b]; //AbsoluteTiming
r2 = truncate[a, b]; //AbsoluteTiming
r3 = algohi[a, b]; //AbsoluteTiming
r4 = klgr1[a, b]; //AbsoluteTiming
r5 = klgr2[a, b]; //AbsoluteTiming

r1 == r2 == r3 == r4 == r5


{0.002184, Null}

{0.030749, Null}

{0.742536, Null}

{31.082, Null}

{53.734, Null}

True

list0 = {54, 4, 7, 9, 3, 54, 4, 20, 2, 456, 2, 3};
targetList = {2, 3, 4, 7};

Module[{list0chopped = {}, l2 = list0, tg = targetList},
While[l2 =!= {} && tg =!= {},
AppendTo[list0chopped, First[l2]];
tg = Delete[tg, FirstPosition[tg, l2[], {}, {1}]];
l2 = Rest[l2]
];
list0chopped]


{54, 4, 7, 9, 3, 54, 4, 20, 2}

If the same element appears several times in targetList, it should appears the same number of times in list0 before list0chopped is returned