# How many laps around the permutation?

Your input is an array of numbers: a permutation of $$\\{1, 2 \dots n\}\$$ for some integer $$\n \geq 2\$$.

How many times must you repeat this list before you can "pick out" the numbers $$\[1, 2 \dots n]\$$ in order?

That is: find the lowest $$\t \geq 1\$$ so that $$\[1, 2 \dots n]\$$ is a subsequence of $$\\text{repeat}(\text{input}, t)\$$.

This is : write the shortest program or function that accepts a list of numbers and produces $$\t\$$.

## Example

For [6,1,2,3,5,4], the answer is 3:

6,1,2,3,5,4    6,1,2,3,5,4    6,1,2,3,5,4
^ ^ ^   ^            ^      ^


## Test cases

[2,1] -> 2
[3,2,1] -> 3
[1,2,3,4] -> 1
[4,1,5,2,3] -> 2
[6,1,2,3,5,4] -> 3
[3,1,2,5,4,7,6] -> 4
[7,1,8,3,5,6,4,2] -> 4
[8,4,3,1,9,6,7,5,2] -> 5
[8,2,10,1,3,4,6,7,5,9] -> 5
[8,6,1,11,10,2,7,9,5,4,3] -> 7
[10,5,1,6,11,9,2,3,4,12,8,7] -> 5
[2,3,8,7,6,9,4,5,11,1,12,13,10] -> 6


# Jelly, 5 bytes

Ụ>ƝS‘


Try it online!

Ụ     -- Grade up. Indices that would sort the input
>Ɲ   -- For each pair of adjacent values, is the left larger than the right?
S  -- Sum the boolean results
‘ -- Increment by 1


# Python 3, 36 bytes

f=lambda x,*p:p==()or(x-1in p)+f(*p)


Try it online!

The number of repeats needed is equal to the number of pairs x and x+1 such that the x+1 appears before x in the permutation, plus one.

# Julia 1.0, 30 bytes

a->sum(diff(sortperm(a)).<0)+1


Try it online!

-2 bytes thanks to @dingledooper.

• I believe sum works in place of count. Commented Feb 4, 2022 at 5:30
• Thanks. Julia is usually fussy about keeping Bools and Ints distinct, so I didn't expect that to work! Commented Feb 4, 2022 at 5:41

# Vyxal, 6 bytes

⇧¯0<∑›


Try it Online!

⇧      # Grade up
¯0<   # Cumulative differences less than 0
∑› # Sum + 1

• i was 24 hours too late :( Commented Feb 5, 2022 at 10:24

# Wolfram Language (Mathematica), 3331 30 bytes

-1 thanks to alephalpha

Count[#-##2&@@@#~Subsets~2,1]&


Try it online!

Input [list].

Doesn't work for $$\n=1\$$, but we're guaranteed $$\n\ge 2\$$.

### Wolfram Language (Mathematica), 37 36 bytes

Tr@Boole[Set@a;Set[a,#,a]!=#-1&/@#]&


Try it online!

The number of repeats is also equal to the number of prefixes ...,x that don't contain x-1.

         Set@a;                     clear prefix
&/@#  for each:
#-1        predecessor
Set[a,#,a]!=           not in prefix
Tr@Boole[                         ] count

• Count[#~Subsets~{2}.{1,-1},1]+1& Commented Feb 4, 2022 at 3:00

# R, 34 bytes

function(l)sum(diff(order(l))<0)+1


Try it online!

Port of e.g., Sundar R's answer.

# R, 7769 67 bytes

function(l){while(all(combn(rep(l,T),max(l),is.unsorted)))T=T+1
+T}


Try it online!

Brute force: combn(rep(input,t),max(input)) generates all length(input) subsequences of $$\\text {repeat}(\text {input},t)\$$, and check for one that is sorted.

-2 bytes thanks to pajonk.

• I think here length(input)=max(input), so -2 bytes. Commented Feb 4, 2022 at 6:06
• @pajonk yes, of course, thank you. Commented Feb 4, 2022 at 14:27

Thanks @Unrelated String for -3 bytes

Thanks @Bubbler for another -2 bytes

f[]=1
f(h:t)=sum[1|elem(h-1)t]+f t


Try it online!

Answered as part of the current Haskell LYAL event. Tell me if there are any golfs, this is my first time coding in Haskell.

# Factor, 42 bytes

[ arg-sort differences [ 0 < ] count 1 + ]


## Explanation

Arg-sort the input (i.e. get the indices that sort the input), get their first-order differences, count how many elements are negative, and add one.

               ! { 6 1 2 3 5 4 }
arg-sort       ! { 1 2 3 5 4 0 }
differences    ! { 1 1 2 -1 -4 }
[ 0 < ] count  ! 2
1              ! 2 1
+              ! 3


Try it online!

# MATL, 118 7 bytes

&Sd0<sQ


Try it online!

Straight port of my Julia answer (using the second output of sort in place of sortperm - thanks to @Giuseppe for that idea, saving me 3 bytes).

Another -1 byte thanks to @LuisMendo (so rusty with MATL I forgot & even existed!)

# Octave, 24 bytes

@(a)nnz(tril(a==a'+1))+1


Try it online!

Port of @dingledooper's Python 3 answer.

# APL(Dyalog Unicode), 4938 bytes SBCS

{0=⌈/⍵:1⋄~1∊⍺:1+⍵∇⍵⋄(⍵-1)∇⍨¯1+⍺↓⍨⍺⍳1}⍨


Try it on APLgolf!

A dfn submission which uses recursion (yuck) to keep track of things. Instead of looking for increasing numbers, we decrement the sequence and always look for a 1: this means that, as we recurse, we don't need to keep track of the number we are searching for.

⍺ contains the tail of the sequence where we can still look for 1s, and ⍵ contains a copy of the original sequence, but decremented by the amount of times we already found the next digit.

Then, we just look for the next number in the sequence tail.

• If it's there, chop the sequence tail and call the function recursively, after decrementing the original sequence again and the new tail.
• If it's not there, use ⍵ to reset the sequence tail, and add a 1 to the recursive result because we needed one extra repetition.

Recursion stops when the decremented copy of the original sequence has 0 as its largest element.

@Razetime also shared a “boring Jelly port” in the comments for 8 bytes:

1+1⊥2>/⍋

• Boring Jelly port: 1+1⊥2>/⍋ Commented Feb 4, 2022 at 9:03
• @Razetime lol 🤣 I tried solving this without looking at the other solutions, but didn't expect to be kicked in the butt so spectacularly! Will you post this as a separate solution or should I add it here w/ credit?
– RGS
Commented Feb 4, 2022 at 9:25
• well it isn't particularly novel. I'd rather leave it as a comment and keep your answer unchanged. Commented Feb 4, 2022 at 10:04

# Brachylog, 9 8 bytes

{⊇Ċ-1}ᶜ<


Try it online!

### Explanation

Saved 1 byte by porting everybody else's approach.

{⊇Ċ-1}ᶜ<
{    }ᶜ   Count how many ways there are to satisfy this predicate:
⊇          A subsequence of the input
Ċ         Of length 2
-        Has a difference (first element minus second element)
1       Equal to 1 (first element is 1 + second element)
<  The output is the next integer larger than that result


Old solution that implements the spec directly:

;.j₎⊇~o?∧
;           Pair the input with
.          Some as-yet unknown value which will be the output
j₎        Repeat the former a number of times equal to the latter (trying 0 first,
then 1, then 2, etc., until the rest of the predicate succeeds)
⊇       Some subsequence of the result
~o     Is a sorted version of
?    The input
∧   Output whatever we calculated earlier as .


Try it online!

## Python3, 109 bytes:

from itertools import*
f=lambda x,c=1:c if any(sorted(x)==[*i]for i in combinations(x*c,len(x)))else f(x,c+1)


Try it online!

Brute force solution, extremely slow.

## Python3, 115 bytes:

v=lambda o,n:not o or(o[0]in n and v(o[1:],n[n.index(o[0])+1:]))
f=lambda x,c=1:c if v(sorted(x),x*c)else f(x,c+1)


Try it online!

Much faster version.

• For the slow one: 108 bytes. I just swapped the if else order so you could remove whitespace. You can do the same for the other one for one less byte Commented Feb 3, 2022 at 22:19
• 113 bytes by removing the paranthese after or and the matching parenthesis on the end (along with the extra whitespace at the end?!) Commented Feb 3, 2022 at 22:26

# JavaScript (ES6), 45 bytes

f=(a,k=0)=>a.some(n=>!a[k+=k+1==n])||1+f(a,k)


Try it online!

# K (ngn/k), 8 bytes

1+/<':<:


Try it online!

Essentially a port of @ovs' Jelly answer.

• <: grade-up the input (generates a permutation vector which would sort argument into ascending order)
• <': check if each value is less than its predecessor
• 1+/ take the sum, seeded with 1

# Desmos, 55 bytes

l=sort([1...L.length],L)
f(L)=\total(\{l[2...]<l,0\})+1


Try It On Desmos!

Try It On Desmos! - Prettified

$$\f(L)\$$ takes in a list $$\L\$$ and returns the lowest value of $$\t\$$ as specified in the challenge.

The code basically just does the "grade up" trick that many of the other answers were doing.

# Charcoal, 10 bytes

ＩΣＥθ›κ⌕θ⊕ι


Try it online! Link is to verbose version of code. Based on @dingledooper's observation that the number of repeats is 1 plus the number of times x+1 appears before x, although because Find returns -1 when the value is not found, the formula believes n+1 appears before n, thus automatically adding the extra 1 to the result.

   θ        Input array
Ｅ         Map over values
κ      Current index
›       Is greater than
⌕     Index of
ι  Current value
⊕   Incremented
θ    In input array
Σ          Take the sum
Ｉ           Cast to string
Implicitly print


# 05AB1E, 6 bytes

>kā<‹O


The same approach as @dingledooper's uses in his Python answer.

Explanation:

>       # Increase each value in the (implicit) input-list by 1
k      # Get the index of these values in the (implicit) input-list
# (or -1 for the max+1 that isn't found)
ā     # Push a list in the range [1,length] (without popping the list)
<    # Decrease each by 1 to make the range [0,length)
‹   # Do a smaller than check for the values of the two lists
O  # Sum the amount of truthy values
# (which is output implicitly as result)


# Thunno, $$\ 15 \log_{256}(96) \approx \$$ 12.35 bytes

e1+z0AhEDLRz.<S


Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

e1+z0AhEDLRz.<S  # Implicit input
e      E         # For each number in the input:
1+              #  Increment it
Ah          #  And get the index
DLR      # Duplicate and push [0..length]
z.<   # Do a less than check
S  # Sum the truthy values
# Implicit output


# Uiua, 10 bytes SBCS

+1/+/<⍉◫2⍏


Try it!

# Scala 3, 70 bytes

Golfed version. Attempt This Online!

_.zipWithIndex.sortBy(_._1).map(_._2).sliding(2).count(p=>p(1)<p(0))+1


Ungolfed version.

def f(a: Array[Int]): Int = {
val sortedIndices = a.zipWithIndex.sortBy(_._1).map(_._2)
sortedIndices.sliding(2).count(pair => pair(1) < pair(0)) + 1
}


# Retina 0.8.2, 28 bytes

\d+
$* \b1(1*)\b(?=.*\b\1\b)  Try it online! Link includes test cases. Explanation: Uses @dingledooper's observation again. \d+$*


Convert to unary.

\b1(1*)\b(?=.*\b\1\b)


Count the matches of 1+$.1 that are followed by $.1. When this is positive, the word boundary anchors simply ensure that $.1 is exactly matched, but conveniently when $.1 is 0 we get an extra "false" match which automatically increments the final result for us.

# C (gcc), 70 57 bytes

i;t;f(a,n)int*a;{for(i=t=n;t;)a[i%n]+t+~n?i++:t--;a=i/n;}


Try it online!

Saved a whopping 13 bytes thanks to att!!!

Inputs a pointer to an array of numbers that are a permutation of $$\\{1, 2 \dots n\}\$$ and $$\n\$$ (because pointers in C carry no length info).
Returns how many times this array must be repeated before you can pick out the numbers $$\\{1, 2 \dots n\}\$$ in order.

• brute force 57 bytes: i;t;f(a,n)int*a;{for(i=t=n;t;)a[i%n]+t+~n?i++:t--;a=i/n;}
– att
Commented Feb 4, 2022 at 0:12
• @att Awesome - thanks! :D Commented Feb 4, 2022 at 9:45

array_reduce($a,function($c,$x){return[$x,$c[1]+($x<$c[0])];})[1]+1  Implementation of algorithm from ovs' answer: count all pairs where right < left, then add 1. Since array_reduce takes only one "carry" param, but we want each iteration to know both the running total and the previous value, we make 'carry' be an array with both elements in, which is a few bytes shorter than making a global, but makes a warning the first time we access the (uninitialized) array. Reduced from first submission by moving all calculation into the return. Reduced further since it apparently doesn't need to be a program, just a code snippet that takes an array and outputs a value, so all the boilerplate can go away into a header/footer. Try it online! # Perl 5, 58 bytes sub{$_="@_;"x@_;my$i;1while++$i&&s/.*?\b\$i\b//;1+@_-y/;//}


Try it online!