15
\$\begingroup\$

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 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
\$\endgroup\$
0

8 Answers 8

4
\$\begingroup\$

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: (⊂⍬),.

\$\endgroup\$
2
  • \$\begingroup\$ Once you get the gradeups of the sunseqs, can’t you just check if the input is an elm of that? \$\endgroup\$
    – Jonah
    Feb 25 at 15:03
  • 1
    \$\begingroup\$ @Jonah the subsequences unfortunately do not include the empty one, and the obvious way to add that is longer (See the last paragraph). \$\endgroup\$
    – ovs
    Feb 25 at 15:05
4
\$\begingroup\$

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?
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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()
\$\endgroup\$
3
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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?
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 38 bytes

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

Try it online!

Expects f[A,B].

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.