Is it a sub-permutation?

Question

A finite-permutation is a function which takes an \$n\$-tuple and produces an \$n\$-tuple such that every element of the input is present in the output, and the ordering does not rely on the values of the inputs.

We can unambiguously represent these permutations with an \$n\$-tuple where each element is the index of where it will end up. For example:

$$ (3 \,\, 2 \,\, 1 \,\, 0) $$

This permutation reverses a \$4\$ element tuple. The first element goes to the 3rd (last) position, the second goes to the 2nd (penultimate) position etc.

With this representation a valid permutation is just any list of size \$n\$ which contains the numbers \$0\$ through \$n-1\$.

Now if we want let's apply a permutation, \$(5 \,\, 2 \,\, 1 \,\, 4 \,\, 3 \,\, 0)\$, but first lets color 3 elements red.

$$ (A,\color{red}{B},C,\color{red}{D},\color{red}{E},F) \\ \underset{\,(5 \,\, 2 \,\, 1 \,\, 4 \,\, 3 \,\, 0)\,}{\xrightarrow{}}\\ (F,C,\color{red}{B},\color{red}{E},\color{red}{D},A) $$

Now if we just look at how the permutation effects the order of highlighted elements we get:

$$ (\color{red}{B},\color{red}{D},\color{red}{E}) \\ \longrightarrow{}\\ (\color{red}{B},\color{red}{E},\color{red}{D}) $$

Which is the permutation \$(0\,\,2\,\,1)\$.

One permutation is a sub-permutation of another if it is the permutation acting on some subset of the elements of the tuple. So

$$ (0\,\,2\,\,1)\subseteq(5 \,\, 2 \,\, 1 \,\, 4 \,\, 3 \,\, 0) $$

by the example shown above. Every permutation is a sub-permutaton of itself.

Task

Given two permutations \$A\$ and \$B\$ determine if \$A\$ is a sub-permutation of \$B\$. You should output one of two distinct values. One if \$A\$ is a sub-permutation of \$B\$ and the other if a does not.

This is code-golf so the goal is to minimize your source code as scored in bytes.

You may take permutations in any reasonable format, this includes formats that use 1 indexing instead of 0 indexing.

Test cases

[] [0,1,2] -> True
[0] [0,1,2] -> True
[0,1] [0,1,2] -> True
[0,1,2] [0,1,2] -> True
[1,0] [0,1,2] -> False
[0,1,2,3] [0,1,2] -> False
[] [2,1,0] -> True
[0] [2,1,0] -> True
[0,1] [2,1,0] -> False
[1,0] [2,1,0] -> True
[0,2,1] [2,1,0] -> False
[0,2,1] [3,2,1,0] -> False
[0,2,1] [5,2,1,4,3,0] -> True
[0,1,2] [5,2,1,4,3,0] -> False
[2,1,0] [5,2,1,4,3,0] -> True
[1,2,0] [5,2,1,4,3,0] -> True

Answer 1

APL(Dyalog Unicode), 25 bytes ^SBCS

{⍺≡∊(⊂⍺)∩⍋⍤,¨⊃,/(⊢,,¨)\⍵}

Try it on APLgolf!

⊃,/(⊢,,¨)\⍵ generates all non-empty subsequences and is taken from this tip.
⍋⍤,¨ converts each subsequence to a sub-permutation by getting the indices that would sort the sequence.
(⊂⍺)∩ intersects that list of sub-permutations with the left input.
⍺≡∊ checks if the flattened result of that matches the left argument.

Without dealing with the empty list the last two steps could be (⊂⍺)∊, adding the empty list to the sub-permutations would be longer: (⊂⍬),.

Answer 2

Vyxal, 5 bytes

ṗv⇧$c

Try it Online!

Port of Jonathan Allan's Jelly answer.

ṗ     # Powerset
 v⇧   # Grade up each
   $c # Is the input contained in that?

Answer 3

05AB1E, 8 bytes

æεD{kQ}à

Inputs are in the order \$B,A\$.

Try it online or verify all test cases.

Explanation:

æ       # Get the powerset of the first (implicit) input-list B
 ε      # Map over each list:
  D     #  Duplicate the current list
   {    #  Sort the copy
    k   #  Get the index of each value in the list
     Q  #  Check if this is equal to the second (implicit) input-list B
 }à     # After the map: pop and push the maximum to check if any was truthy
        # (which is output implicitly as result)

Try it online with step-by-step debug lines.

Answer 4

JavaScript (ES6),  74  70 bytes

Expects (A)(B) in 1-indexing format. Returns \$0\$ or \$1\$.

A=>F=([v,...B],C=[0])=>v?F(B,C)|F(B,[...C,v]):A.every(i=>~~v<(v=C[i]))

Try it online!

Commented

A =>                 // A[] = candidate sub-permutation
F = (                // F is a recursive function taking:
  [v,                //   v = next value from the main permutation
      ...B],         //   B[] = remaining values in the main permutation
  C = [0]            //   C[] = subset of B[], with a leading 0 to take
                     //         1-indexing into account
) =>                 //
v ?                  // if v is defined:
  F(B, C) |          //   try a recursive call where C[] is left unchanged
  F(B, [...C, v])    //   try a recursive call where v is added to C[]
:                    // else:
  A.every(i =>       //   for each entry i in A[]:
    ~~v < (v = C[i]) //     make sure that v is less than C[i]
                     //     (v is initially undefined and coerced to 0)
                     //     and update v to C[i]
  )                  //   end of every()

Answer 5

Factor, 47 bytes

[ all-subseqs { } suffix [ arg-sort ] map in? ]

Try it online!

Is the first input in the inverse permutations of the subsequences of the second input?

Answer 6

Jelly, 6 bytes

^{Or only 5 bytes for a count of the ways - ŒPỤ€ċ}

ŒPỤ€e@

A dyadic Link accepting the permutation on the left and the potential sub-permutation on the right (both 1-indexed).

Try it online!

How?

ŒPỤ€e@ - Link: permutation, P; potential sub-permutation, S
ŒP     - powerset (i.e. all sub-sequences) of P
   €   - for each:
  Ụ    -   grade up (1-based indices sorted by their respective values)
     @ - with swapped arguments - f(S, that):
    e  -   S exists in that?

Answer 7

Python3, 117 bytes:

f=lambda x,y,p=0,q=0:not x or(y and(k:=(x[0]-p>=0)==(y[0]-q>=0))and any([f(x[k:],y[k:],x[0],y[0])*k,f(x,y[1:],p,q)]))

Try it online!

Answer 8

Wolfram Language (Mathematica), 38 bytes

MemberQ[(o=Ordering)/@Subsets@#2,o@#]&

Try it online!

Expects f[A,B].