# Efficiently testing if every member of a sublist comes before every other member of another sublist

I have a list of elements -

bigList = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};


And two sublists:

sublistOne = {"H", "B", "D"};
sublistTwo = {"I", "L", "J"};


How do I efficiently create a function f that returns TRUE only if all elements of sublistOne come before all elements of sublistTwo in bigList?

For the provided example, f should return TRUE. However, if we kept the same sublistOne and set sublistTwo = {"I", "F", J"}, f should return false because element F in sublistTwo appears prior to element H in sublistOne.

Please note that I could scramble the English alphabet in bigList and then have the first example return FALSE. The function f should only test the index of each variable and ignore its numeric or string value.

You could use Position to extract the positions of the elements in bigList. Then, you only need to ensure that the biggest position number in the sublistOne is smaller than the smallest position number in sublistTwo

f[big_, s1_, s2_] := Max[#1] < Min[#2] & @@ (Position[big, Alternatives[##]] & @@@ {s1, s2})


Another way:

And @@ MapThread[
Cases[bigList, Alternatives[##], 1, 1] =!= {#2} &,
{sublistOne, sublistTwo}]


As a function, which bails out at the first unordered pair:

ordQ[ordering_, list1_, list2_] := Catch[
If[Cases[ordering, Alternatives[##], 1, 1] === {#2},
Throw[False]] &,
{list1, list2}];
True]

ordQ[bigList, sublistOne, sublistTwo]
(* True *)


Using two new-in-Version-10 variations:

FirstPosition:

pF1=With[{p=FirstPosition[Alternatives@@#]&/@{#1,#2}},
First[Length[#3]-p[[1]]@Reverse@#3]<First[p[[2]]@#3]]&;
pF1[sublistOne,sublistTwo,bigList]
(* True *)


Operator form of Position:

pF2=With[{p=Position[Alternatives@@#]&/@{#1,#2}},   Max[p[[1]]@#3]<Min[p[[2]]@#3]]&;
pF2[sublistOne,sublistTwo,bigList]
(* True *)


I could scramble the English alphabet ... The function f should only test the index of each variable and ignore its numeric or string value.

This task is a natural fit for PositionIndex but not as much for Interval, although I will try to stretch it a bit as it allows for visualization using NumberLinePlot.

bigList = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L",
"M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y",
"Z"};
pi = PositionIndex[bigList];

sublist1 = {"H", "B", "D"};
sublist2 = {"I", "L", "J"};
sublist3 = {"I", "F", "J"};


Define a function that determines the Interval using the position index called pi:

f[k_List] := Interval[MinMax[k /. pi // Flatten]]

{f@sublist1, f@sublist2, IntervalIntersection[f@sublist1, f@sublist2]}


{Interval[{2, 8}], Interval[{9, 12}], Interval[]}

For visualization:

ticks = Transpose[{Sequence @@@ Values@pi, Keys@pi}]
NumberLinePlot[{
Values@pi, f@sublist1, f@sublist2
, IntervalIntersection[f@sublist1, f@sublist2]
}
, Ticks -> {ticks, Automatic}
]


With sublist3:

{f@sublist1, f@sublist3, IntervalIntersection[f@sublist1, f@sublist3]}


{Interval[{2, 8}], Interval[{6, 10}], Interval[{6, 8}]}

Now let's scramble the bigList:

SeedRandom[2];
newBigList = RandomSample[bigList, 26]
pi = PositionIndex[newBigList];
s1 = Characters@"CUZ";
s2 = Characters@"ICAN";
{f[s1], f[s2], IntervalIntersection[f[s1], f[s2]]}


{Interval[{24, 26}], Interval[{7, 24}], Interval[{24, 24}]}

ticks = Transpose[{Sequence @@@ Values@pi, Keys@pi}]
NumberLinePlot[{
Values@pi, f@s1, f@s2, IntervalIntersection[f[s1], f[s2]]
}
, Ticks -> {ticks, Automatic}
]