How many laps around the permutation?

Question

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 code-golf: 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

Answer 1

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

Answer 2

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.

Answer 3

Julia 1.0, 30 bytes

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

Try it online!

-2 bytes thanks to @dingledooper.

Answer 4

Vyxal, 6 bytes

⇧¯0<∑›

Try it Online!

Port of ovs's jelly answer.

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

Answer 5

Wolfram Language (Mathematica), 33 31 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

Answer 6

R, 34 bytes

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

Try it online!

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

R, 77 69 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.

Answer 7

Haskell, 39 34 bytes

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!

Port of @dingledooper's Python answer

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

Answer 8

Factor, 42 bytes

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

Port of @SundarR's Julia answer.

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!

Answer 9

MATL, 11 8 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!)

Answer 10

Octave, 24 bytes

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

Try it online!

Port of @dingledooper's Python 3 answer.

Answer 11

APL(Dyalog Unicode), ⁴⁹38 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>/⍋

Answer 12

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!

Answer 13

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.

Answer 14

JavaScript (ES6), 45 bytes

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

Try it online!

Answer 15

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

Answer 16

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.

Answer 17

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

Answer 18

05AB1E, 6 bytes

>kā<‹O

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

Try it online or verify all test cases.

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)

Answer 19

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.

Answer 20

C (gcc), ⁷⁰ 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.

Answer 21

PHP, 81 74 67 bytes

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!

Answer 22

Perl 5, 58 bytes

sub{$_="@_;"x@_;my$i;1while++$i&&s/.*?\b$i\b//;1+@_-y/;//}

Try it online!

Answer 23

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
   z0            #  in the input (-1 if not found)
        DLR      # Duplicate and push [0..length]
           z.<   # Do a less than check
              S  # Sum the truthy values
                 # Implicit output