[Question]
  [
Yesterday I asked [this](https://codegolf.stackexchange.com/q/152281/56656) question about riffle shuffles. It seems that yesterdays question was a bit too hard so this question is a related but much easier task.
Today you are asked to determine if a permutation is in fact a riffle shuffle. Our definition of riffle shuffle is adapted from our last question: 
The first part of the shuffle is the divide. In the divide partition the deck of cards in two. The two subsections must be continuous, mutually exclusive and exhaustive. In the real world want to make your partition as close to even as possible, however in this challenge this is not a consideration, all partitions including ones that are degenerate (one partition is empty) are of equal consideration.
After they have been partitioned, the cards are spliced together in such a way that cards maintain their relative order *within the partition they are a member of*. For example, if card **A** is before card **B** in the deck and cards **A** and **B** are in the same partition, card **A** must be before card **B** in the final result, even if the number of cards between them has increased. If **A** and **B** are in different partitions, they can be in any order, regardless of their starting order, in the final result.
Each riffle shuffle can then be viewed as a permutation of the original deck of cards. For example the permutation
```
1,2,3 -> 1,3,2
```
is a riffle shuffle. If you split the deck like so
```
1, 2 | 3
```
we see that every card in `1,3,2` has the same relative order to every other card in it's partition. `2` is still after `1`.
On the other hand the following permutation is *not* a riffle shuffle.
```
1,2,3 -> 3,2,1
```
We can see this because for all the two (non-trivial) partitions
```
1, 2 | 3
1 | 2, 3 
```
there is a pair of cards that do not maintain their relative orderings. In the first partition `1` and `2` change their ordering, while in the second partition `2` and `3` change their ordering.
## Task
Given a permutation via any reasonable method, determine if it represents a valid riffle shuffle. You should output two distinct constant values one for "Yes, this is a riffle shuffle" and one for "No, this is not a riffle shuffle".
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so answers will be scored in bytes with less bytes being better.
## Test Cases
```
1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False
```
  
[Answer]
# JavaScript (ES6), 47 bytes
Takes input as an array of integers. Returns a boolean.
```
([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)
```
### Test cases
```
let f =
([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)
;[
  [1,3,2      ],  // -> True
  [3,2,1      ],  // -> False
  [3,1,2,4    ],  // -> True
  [2,3,4,1    ],  // -> True
  [4,3,2,1    ],  // -> False
  [1,2,3,4,5  ],  // -> True
  [1,2,5,4,3  ],  // -> False
  [3,1,4,2,5  ],  // -> True
  [2,3,6,1,4,5]   // -> False
]
.forEach(a => console.log(JSON.stringify(a) + ' -> ' + f(a)))
```
### How?
The input array **A** is a valid riffle shuffle if it consists of at most two distinct interlaced sequences of consecutive integers.
The challenge rules specify that we're given a *permutation* of **[1...N]**. So we don't need to additionally check that the sorted union of these sequences actually results in such a range.
We use a counter **x** initialized to **A[0]** and a counter **y** initially undefined.
For each entry **z** in **A**, starting with the 2nd one:
* We check whether **z** is equal to either **x+1** or **y+1**. If yes, we increment the corresponding counter.
* Else: if **y** is still undefined, we initialize it to **z**.
* Else: we make the test fail.
[Answer]
# [Haskell](https://www.haskell.org/), 41 bytes
```
n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l
```
[Try it online!](https://tio.run/##PY5BCsMgEEX3OcUsEjBowUS79CRiQKjB0NGGtPe31qGuZt78x2eifz8DYil5iiZzubF8i/O2DjugCRgS21/4QDbNckTOccaCxlopYBWwOGF/Q4CkTTZQFZYmKEoU2QTkUKg768ZrZd1qFFm9llj35vv/qp0bkj8yGIDzOvIHRkj@hPp/@QI "Haskell – Try It Online")
Checks if the list concatenated to itself contains the numbers `0..n-1` in order as a subsequence.
[Answer]
# [Haskell](https://www.haskell.org/), 43 bytes
`s` takes a list of integers as in the OP examples and returns a `Bool`.
```
s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter
```
[Try it online!](https://tio.run/##NY1BDoMgEEX3noI0XUBAEhR34kUoC9JCJEUlYlMXvTsdTbuZefnvT2a0@eliLJMNswrz5lZ7366vOYbZZT7ZhG@pHhKlF1QP6EJpHpc3znh19oESIYSfzZJRUsuqPe53Am2PBwXQa8G5@ex9nUzllQ8RHpSiBWtZYyoNk4lzCyAJ1ICRZybZ3x7uSLsfd8AtcAdX8nCm@gI "Haskell – Try It Online")
# How it works
* The list comprehension tries each element `x` of `p` in turn and checks if it can be the first element of the second partition of the shuffle. Then `or` returns `True` if any of the checks were `True`.
* The comprehension does this by partitioning (with `filter`) `p` into elements smaller and larger than (or equal to) `x`, concatenating, and checking if the resulting list is `[1..length p]`, i.e. the elements in order.
* The check for whether the resulting list is `[1..length p]` is done by seeing if the result is strictly smaller than the infinite list `[1..] == [1,2,3,etc.]`, which gives the same result for any permutation.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~13~~ 6 bytes
```
ỤIṢḊRẠ
```
[Try it online!](https://tio.run/##y0rNyan8///h7iWeD3cuerijK@jhrgX/D7c/aloT@f9/dLShjoKxjoJRrA6XQjSIoaNgCGMbgrkmYK4RWJkJTNYEogvGhaiEKDBFEjEFixiDRUzBBppAVCJZARExRbLFDCZuGhsLAA "Jelly – Try It Online")
### Alternate version, postdates challenge, 5 bytes
```
Ụ>ƝSỊ
```
[Try it online!](https://tio.run/##y0rNyan8///h7iV2x@YGP9zd9f9w@6OmNZH//0dHG@ooGOsoGMXqcClEgxg6CoYwtiGYawLmGoGVmcBkTSC6YFyISogCUyQRU7CIMVjEFGygCUQlkhUQEVMkW8xg4qaxsQA "Jelly – Try It Online")
### How it works
```
ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])
Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.
```
[Answer]
# [Python 2](https://docs.python.org/2/), 39 bytes
```
l=input()
n=0
for x in l*2:n+=n==x
l[n]
```
[Try it online!](https://tio.run/##TYw9C8MgEEB3f8WRqR8ZjNol4NhC924hQ0ksEeQUa6j59WlUGjrdvbvHc0uYLLJ1sKOSVVWtRmp0czgcCUpKXtZDBI1gTqzFs0QpIzEd9uvmks@kjYKHn1VLAIJf0gBQUQ2Qgpmc1xjg9jTvxCoOygW446ji1Xvr2z8pldaO1sBqaHrSpVEDLRvNwDdossDLhxe7QHHKU@wsMrONRc7wYu3ZwmIvX35X0X8B "Python 2 – Try It Online")
Takes the list 0-indexed and outputs via exit code.
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 9 bytes
```
o~cĊ⟨⊆⊇⟩?
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/pf/ahtw6Ompkcdy5VKikpTlWpArLTEnOJUpdqHWyeU/8@vSz7S9Wj@ikddbY@62h/NX2n//390tKGOsY5RrE40kNQxBNOGQJYJkGUElDEBi5nowGRBciBRUyjbFMg2BrJNgbpMQHJQE0BsU6gZZmC@aWwsAA "Brachylog – Try It Online")
The predicate succeeds if the input represents a riffle shuffle and fails if it does not, meaning among other things that if the predicate is run as an entire program success will print `true.` and failure will print `false.`. Input is taken as a list of any sorts of items and interprets it as representing a permutation of itself sorted.
```
   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.
```
I feel like there's something in the spirit of `⊆ᵐ` which should work in the place of the four-byte "sandwich" construct `⟨⊆⊇⟩`.
[Answer]
# [Python 2](https://docs.python.org/2/), ~~75~~ ~~60~~ 47 bytes
thanks to Dennis for -13 bytes
```
x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q
```
[Try it online!](https://tio.run/##TYzNDoIwEITvfYoNJ0lqIj/1QMSbHvXizXhAXCMRaa0Fa5Bnxy3BaNJ0v9mZHfUyF1mFfS5PmHqe19u0nXXsLDU0UFT0VG0mfmJTO22badC926ZjJVYT6y@i5b2nG/a8FCXCTteYMACjX24AoMUcXPGglC4qA@usfDiNNkdlYJPdcKW11MlfxhX9Iqvt@i9x1Jhd@33AIx4e2J5@HgwzIIqJQnLiYRfzr@s8txUjC@KIWNBV7LyxwbEYO@aDFocP "Python 2 – Try It Online")
Output is via exit code.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 35 bytes
```
->l{l.any?{|a|l&[*1..a]|l==l.sort}}
```
[Try it online!](https://tio.run/##KypNqvyfZvtf1y6nOkcvMa/SvromsSZHLVrLUE8vMbYmx9Y2R684v6iktvZ/QWlJsUJadLShjrGOUWwsF4wP5OkYovANgSImSCJGQB0mKGpMdNB1gfSAVJmiiZkCxYyRxEyBppuA1KLZCBIzRbPTDCwOFP0PAA "Ruby – Try It Online")
## How?
* `l & [*1..a] | l` applies an intersection and then an union: first get the elements of `l` that are `<=a` and then add the remaining elements of `l` without changing the order. If a is the number we are looking for, then this operation is the same as sorting `l`.
[Answer]
# [Clean](https://clean.cs.ru.nl), ~~56~~ 55 bytes
```
import StdEnv
?l=any(\e=sortBy(\a b=a<e&&b>=e)l<[1..])l
```
[Try it online!](https://tio.run/##S85JTcz7n5ufUpqTqpCbmJn3PzO3IL@oRCG4JMU1r4zLPsc2Ma9SIybVthgo6gRkJSok2SbapKqpJdnZpmrm2EQb6unFaub8Dy5JBGqzVbCPNtIx1jHTMdQx0TGN/f8vOS0nMb34v66nz3@XyrzE3MzkYgA "Clean – Try It Online")
[Answer]
## Pyth, 5 bytes
```
}SQy+
```
**[Test suite](https://pyth.herokuapp.com/?code=%7DSQy%2B&test_suite=1&test_suite_input=%5B1%2C3%2C2%5D%0A%5B3%2C2%2C1%5D%0A%5B3%2C1%2C2%2C4%5D%0A%5B2%2C3%2C4%2C1%5D%0A%5B4%2C3%2C2%2C1%5D%0A%5B1%2C2%2C3%2C4%2C5%5D%0A%5B1%2C2%2C5%2C4%2C3%5D%0A%5B5%2C1%2C4%2C2%2C3%5D%0A%5B3%2C1%2C4%2C2%2C5%5D%0A%5B2%2C3%2C6%2C1%2C4%2C5%5D&debug=1)**
```
}SQy+
    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted 
```
Checks whether the doubled input list contains a sorted version of itself as a subsequence.
Thanks to Erik the Outgolfer for 1 byte taking better advantage of implicit input with `+QQ` rather than `*2Q`.
[Answer]
# [Pyth](https://pyth.readthedocs.io), 9 bytes
```
!t-.+xLQS
```
**[Test suite.](https://pyth.herokuapp.com/?code=%21t-.%2BxLQS&test_suite=1&test_suite_input=%5B1%2C3%2C2%5D%0A%5B3%2C2%2C1%5D%0A%5B3%2C1%2C2%2C4%5D%0A%5B2%2C3%2C4%2C1%5D%0A%5B4%2C3%2C2%2C1%5D%0A%5B1%2C2%2C3%2C4%2C5%5D%0A%5B1%2C2%2C5%2C4%2C3%5D%0A%5B5%2C1%2C4%2C2%2C3%5D%0A%5B3%2C1%2C4%2C2%2C5%5D%0A%5B2%2C3%2C6%2C1%2C4%2C5%5D&debug=0)**
Saved 3 bytes thanks to [isaacg](https://codegolf.stackexchange.com/users/20080/isaacg).
# [Pyth](https://pyth.readthedocs.io), 14 bytes
```
}SQm.nS.Tcd2./
```
**[Try it here!](https://pyth.herokuapp.com/?code=%7DSQm.nS.Tcd2.%2F&input=%5B2%2C3%2C6%2C1%2C4%2C5%5D&debug=0)** or **[Verify all the test cases.](https://pyth.herokuapp.com/?code=%7DSQm.nS.Tcd2.%2F&test_suite=1&test_suite_input=%5B1%2C3%2C2%5D%0A%5B3%2C2%2C1%5D%0A%5B3%2C1%2C2%2C4%5D%0A%5B2%2C3%2C4%2C1%5D%0A%5B4%2C3%2C2%2C1%5D%0A%5B1%2C2%2C3%2C4%2C5%5D%0A%5B1%2C2%2C5%2C4%2C3%5D%0A%5B5%2C1%2C4%2C2%2C3%5D%0A%5B3%2C1%2C4%2C2%2C5%5D%0A%5B2%2C3%2C6%2C1%2C4%2C5%5D&debug=0)**
Outputs `True` and `False` for riffle-shuffle and non-riffle-shuffle respectively.
### How?
```
}SQm.nS.Tcd2./ ~ Full program. Reads input from STDIN and outputs to STDOUT.
            ./ ~ Return all divisions of the input into disjoint substrings (partition).
   m           ~ Map over the above using a variable d.
         cd2   ~ Chop d into two-element lists.
       .T      ~ Justified transpose, ignoring absences.
      S        ~ Sort (lexicographically).
    .n         ~ Deep-flatten.
}              ~ Check if the above contains...
 SQ            ~ The sorted input.
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 7 bytes
```
±§#OoṖD
```
**[Test suite!](https://tio.run/##yygtzv6f@6ip8f@hjYeWK/vnP9w5zeX////R0YY6xjpGsTrRQFLHEEwbAlkmQJYRUMYELGaiA5MFyYFETaFsUyDbGMg2BeoyAclBTQCxTaFmmIH5prGxAA "Husk – Try It Online")**
[Answer]
# Perl, 28 bytes
Includes `+1` for `a`
Input on STDIN, 1 based
```
perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"
```
Uses [xnor's algorithm](https://codegolf.stackexchange.com/a/152432/51507)
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 61 bytes
```
a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}
```
[Try it online!](https://tio.run/##jdC9CsIwFIbhWa9CCkJ@TqGpqUNDlPQ21CGpRDpYpbiVXnvMKYigHTJlefLmI21@a9sQLDholCdd/2KGjv4xEKudbrRQzCjDObU5M8eGaWYODlw8as6tikRN4W67ntBxvXoOMeBJJjZ1vdlez30GnmD0dKGjgB2UUEyUqq8sliQ68SvFshTRyiRbxvflf3dxgYT0DbgAy1VSGXUF2E/RVdwg537qb8i5n9LG6n6@8fFTeAM "C (gcc) – Try It Online")
]