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

Question

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?

Answer 1

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.

Answer 2

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])]]]

Answer 3

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}

Answer 4

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}

Answer 5

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

Answer 6

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]], {}, {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