# Is this a Permutation of 1..n

Input a non-empty array with $$\n\$$ positive integers. Test if the input array contains every integer in $$\1\cdots n\$$.

In case you prefer 0-indexed numbers, you may choose to input an array of non-negative integers, and test if the input array contains every integer in $$\0\cdots (n-1)\$$ instead. All testcases and formula listed below use 1-index. You may need to adjust them if you choose this option.

## Input / Output

Input is an array $$\A\$$ with $$\n\$$ positive integers:

$$A = \left[A_1,\dots,A_n\right]$$ $$\forall i \in \left[1,\dots,n\right]: A_i>0$$

Output if input $$\A\$$ satisfies:

$$\forall i \in \left[1,\dots,n\right]: i \in A$$

Output would be two distinct values, or truthy vs falsy values (swap meaning of truthy / falsy is allowed).

## Rules

• This is , shortest code wins. And since this is code-golf, don't worry about time / memory complexity of your code. You may even timeout on TIO as long as your program works when giving it more time to run.

## Testcases

### Truthy

1
1,2
2,1
1,3,2
3,1,2
1,2,3,4,5,6,7,8,9,10,11,12
12,11,10,9,8,7,6,5,4,3,2,1
6,3,8,12,1,10,4,2,7,9,5,11
16,37,14,15,23,8,29,35,21,6,5,34,38,9,36,26,24,32,28,7,20,33,39,12,30,27,40,22,11,41,42,1,10,19,2,25,17,13,3,18,31,4


### Falsy

2
12
1,1
1,3
2,3
3,3
2,1,3,2
1,4,3,1
4,1,2,4
1,2,2,5,5
1,3,3,3,5
8,7,5,3,4,1,6
5,7,1,4,6,1,8,3
6,3,5,4,7,1,8,1,2
6,5,3,8,2,7,9,4
1,1,1,1,1,1,1,1
1,5,9,13,11,7,3
14,6,12,4,10,8,16,2
34,33,38,17,35,11,36,31,28,14,6,15,18,2,19,40,29,41,9,1,27,23,20,32,26,25,37,8,13,30,39,7,5,3,21,4,11,16,10,22,12,24
38,27,20,23,31,6,2,24,21,31,33,7,26,12,14,17,3,2,28,31,5,23,28,27,37,32,7,39,22,6,35,42,19,3,35,17,35,40,22,13,27,7

• is empty list falsy? Jun 24, 2021 at 6:45
• @Razetime IMO, empty list should be truthy. But anyway, empty list is excluded from testcases, and it is undefined behavior to your program.
– tsh
Jun 24, 2021 at 6:48
• How do you feel about restricting to n<10? It would make the elements to check finite and all single digit. And that would allow lots of wacky tarpits to solve it and not require as high a computational class! I think the spirit would still be preserved, and I can’t think of any way it could be used to hardcode or “cheat” that wouldn’t just be longer than doing it “right,” for the languages that can do it. Jun 24, 2021 at 8:20
• @AviFS If your language doesn't support decimal number I/O, you can use character value I/O. If it doesn't support that either, you can take it in binary or unary. Computational class is not a problem; taking lots of time or memory is allowed by default (even if it can't be run to completion realistically on any machine). You're even allowed to handwave the inputs exceeding the limit of the built-in integer representation. So I don't see any extra benefit of restricting the input size to <10. Jun 24, 2021 at 9:13
• Would outputting 0 for one result or any other integer for the other be acceptable? Jun 24, 2021 at 14:03

# Pyt, 6 bytes

şĐŁř=Π


Try it online!

ş              implicit input; sort in ascending order
Đ             duplicate
Ł            get length
ř           push [1,2,... length]
=          element-wise equal with sorted array?
Π         product of booleans; implicit print


returns 1 if permutation of [1,2,...]; 0 otherwise

# Japt, 4 3 bytes

0-based

Íe¶


Saved a byte thanks to Etheryte pointing out one of my own favourite tricks that I somehow forgot!

Íe¶     :Implicit input of array
Í       :Sort
e      :Every?
¶     :  Equal to its 0-based index

• You can use a shortcut for sorting for 3 bytes: Íe¶ Jun 24, 2021 at 20:04
• @Etheryte, of course I can :facepalm: One of my own favourite tricks and I fecking forgot it! Thanks :) Jun 25, 2021 at 20:45
• [0,3,0,3] seems to incorrectly output 0... Jan 16 at 23:25

# Regex (ECMAScript+(?^=)RME), 37 30 28 bytes

(:x*)x\b(.*\1x:|(?^!.*\1\b))


Takes its input in unary, as a concatenation of strings of x characters whose lengths represent the numbers, separated and enclosed on both sides by : characters. Example: :xxx:x:xx: represents 3,1,2.

Try it on replit.com - ECMAScript+(?^=) (RegexMathEngine -xli)

Asserts that there exists no element $$\n\$$ for which there either is a subsequent duplicate element $$\n\$$, or for which there doesn't exist any element $$\n-1\$$ anywhere in the list if $$\n\ne 1\$$.

Returns "match" for falsy and "no match" for truthy (inverted logic).

              # No anchor - can match starting at any point in the string
(:x*)x\b      # Start at any list element; \1 = {that element} - 1, including
# the bounding character on its left side, consuming it without
# consuming the bounding character following it.
(
.*\1x:    # Match any subsequent list element whose value equals \1 + 1
|         # or...
(?^!      # Negative lookinto - assert that the following pattern cannot
# match the entire input string:
.*    # Skip to any list element, putting it in tail (Works in concert
# with the following expression's matching of the left-side
# bounding character contained in \1)
\1\b  # Assert that tail==\1, or if \1==0 this can match at the edge
# of any element in the list (if we didn't need \1==0 to be able
# to match, we could have used "\1:" instead)
)
)


Using comma delimiting (e.g. xxx,x,xx) instead of this input method, would take +5 bytes:

\b(x*)x\b(.*,\1x\b|(?^!.*\b\1\b))


# Regex (PCRE+(?^=)RME), 29 bytes

^:(x*:(?^=.*:((?(2)\2)x):))*$ Try it on replit.com - PCRE+(?^=) (RegexMathEngine --pcre -xli) Golfwise, this is obsoleted by the 28 byte version above, but is kept here due to still being close in length, and using a different algorithm. Iterate once for each list element: Find a list element whose value is the index of the current loop iteration. (Uses a nested backreference to accomplish this.) Returns "match" for truthy and "no match" for falsy. ^ # Anchor to start : # Consume initial bounding character ( # Loop the following: x*: # Consume one list element (?^= # Lookinto - is matched against the entire string .*: # Skip to any list element, putting it in tail ( # \2 = the following: (?(2)\2) # If \2 is set (i.e., if we're not on the first iteration) # then include the previous value of \2 in its new value x # Append one more "x" (if this is the first iteration, # captures just one) ) : # Consume one bounding character ) )* # Iterate the above as many times as possible, minimum 0$                     # Assert we've reached the end of the string


Using comma delimiting (e.g. xxx,x,xx) instead of this input method, would take +2 bytes:

^(x+,?(?^=.*\b((?(2)\2)x)\b))*$ But that regex is incredibly slow, and it takes another +1 byte to give it reasonable speed: ^(x++,?(?^=.*\b((?(2)\2)x)\b))*$


# Regex (ECMAScript 2018 / Pythonregex / .NET), 38 31 29 bytes

(:x*)x\b.*(\1x:|$(?<!\1\b.*))  Try it online! - ECMAScript 2018 Try it online! / Attempt This Online! - Python (with regex) Try it online! - .NET A port of the 37 30 28 byte version, using variable-length right-to-left evaluated lookbehind instead of lookinto. Like it, returns "match" for falsy and "no match" for truthy (inverted logic).  # No anchor - can match starting at any point in the string (:x*)x\b # Start at any list element; \1 = {that element} - 1, including # the bounding character on its left side, consuming it without # consuming the bounding character following it. .* # Skip to any subsequent position in the string ( \1x: # Match any subsequent list element whose value equals \1 + 1 | # or...$          # Assert that we're at the end of the string
(?<!       # Negative lookbehind - using right-to-left evaluation starting
# from the current position (so read this from bottom to top),
# assert that the following cannot match:
\1\b   # Assert that head==\1, or if \1==0 this can match at the edge
# of any element in the list (if we didn't need \1==0 to be able
# to match, we could have used "\1:" instead)
)
)


Using comma delimiting (e.g. xxx,x,xx) instead of this input method, would take +5 bytes:

\b(x*)x\b.*(,\1x\b|$(?<!\b\1\b.*))  Try it online! - ECMAScript 2018 # Regex (.NET), 36 35 bytes ^:(x*:(?=.*(?<=:(x(?(2)\2)):.*)))*$


Try it online!

Golfwise, this is obsoleted by the 29 byte version directly above, but is kept here due to still being close in length, and using a different algorithm.

A port of the 29 byte PCRE+(?^=)RME version, using variable-length right-to-left evaluated lookbehind instead of lookinto. Like it, returns "match" for truthy and "no match" for falsy.

^                     # Anchor to start
:                     # Consume initial bounding character
(                     # Loop the following:
x*:               # Consume one list element
.*            # Skip to later in the string (".*$" would be faster) (?<= # Lookbehind - evaluated right-to-left (so read this # from bottom to top) : # Consume one bounding character # Assert head==1 (on the first iteration) or head==\2+1 (on # subsequent iterations), capturing this as the new value of \2 ( x # Append one more "x" (if this is the first iteration, # captures just one) (?(2)\2) # If \2 is set (i.e., if we're not on the first # iteration) then include the previous value of # \2 in its new value ) :.* # Skip to any list element, putting it in head ) ) )* # Iterate the above as many times as possible, minimum 0$                     # Assert we've reached the end of the string


Using comma delimiting (e.g. xxx,x,xx) instead of this input method, would take +2 bytes:

^(x+,?(?=.*(?<=\b(x(?(2)\2))\b.*)))*$ But that regex is incredibly slow, and it takes another +2 bytes to give it reasonable speed: ^(x+\b,?(?=.*(?<=\b(x(?(2)\2))\b.*)))*$


Try it online!

# Regex (ECMAScript 2018 / Java / Pythonregex / .NET), 44 37 35 bytes

(:x*)x\b(.*\1x:|(?<!(?=.*\1\b)^.*))


Try it online! - ECMAScript 2018
Try it online! - Java
Try it online! / Attempt This Online! - Python (with regex)
Try it online! - .NET

Based on the 37 30 28 byte version (inverted logic).

Java needs to be "hinted" as to how far the lookbehind should go, thus necessitating the use of a lookahead inside the lookbehind.

# Regex (ECMAScript+(?*)RME / PCRE2 v10.35+), 41 39 bytes

^(?*.*(:x*)x:)((.*\1x\b){2}|(?!.*\1\b))


Try it on replit.com - ECMAScript+(?*) (RegexMathEngine -xml)
Attempt This Online! - PCRE2 v10.40+

A port of the 38 31 29 byte version, using molecular lookahead instead of variable-length right-to-left evaluated lookbehind. Like it, returns "match" for falsy and "no match" for truthy (inverted logic).

^                # Anchor to start
(?*              # Molecular (non-atomic) lookahead - try all possible matches
.*(:x*)x:    # Skip to any list element; \1 = {the element} - 1, including
# the bounding character on its left side
)
(
(
.*\1x\b  # Match and consume any subsequent list element whose value
# equals \1 + 1, without consuming the bounding character on
# its right side (to allow this group to be repeated)
){2}         # Iterate the above 2 times
|          # or...
(?!          # Negative lookahead - assert that the following cannot match:
.*       # Skip to any list element, putting it in tail (Works in
# concert with the following expression's matching of the
# left-side bounding character contained in \1)
\1\b     # Assert that tail==\1, or if \1==0 this can match at the edge
# of any element in the list (if we didn't need \1==0 to be
# able to match, we could have used "\1:" instead)
)
)


# Regex (ECMAScript+(?*)RME / PCRE2 v10.35+), 44 42 bytes

^(?!.*(:x*)\b.*\1:|(?*.*(:x+)x:)(?!.*\2:))


Try it on replit.com - ECMAScript+(?*) (RegexMathEngine -xml)
Attempt This Online! - PCRE2 v10.40+

Asserts that there exists no element $$\n\$$ for which there is a subsequent duplicate element $$\n\$$, and that there exists no element $$\n≥2\$$ for which there is no element $$\n-1\$$ anywhere in the list.

Returns "match" for truthy and "no match" for falsy.

This non-inverted logic version is being kept up, despite losing in golf to the inverted logic 41 39 byte version above, to show how close it comes in length. This is because the second half of the logic, that asserts there are no non-consecutive elements, cannot be golfed by inverted logic, since the .*: must be inside the molecular lookahead.

^                  # Anchor to start
(?!                # Negative lookahead - assert that the following cannot match:
.*(:x*)\b      # Skip to any list element; \1 = the element, including the
# bounding character on its left side
.*             # Skip to any list element, putting it in tail (Works in
# concert with the following expression's matching of the
# left-side bounding character contained in \1)
\1:            # Assert tail == \1
|              # or...
(?*            # Molecular (non-atomic) lookahead - try all possible matches
.*(:x+)x:  # Skip to any list element that's ≥ 2; \2 = {the element} - 1,
# including the bounding character on its left side
)
(?!            # Negative lookahead - only matches outside if the pattern
# inside fails to match.
.*         # Skip to any list element, putting it in tail (Works in
# concert with the following expression's matching of the
# left-side bounding character contained in \2)
\2:        # Assert tail == \2
)
)


# C# (Visual C# Interactive Compiler), 46 bytes

a=>{a.Sort();int i=1;return a.All(x=>x==i++);}


Try it online!

• 1,1,1,1,1,1 should be false
– tsh
Jun 24, 2021 at 7:38
• The third test case in your TIO link should be false. That said, removing Distinct should fix it. Jun 24, 2021 at 7:50
• I had one of the falsey test cases with my truthy ones, that's what tripped me up, thanks Jun 24, 2021 at 9:00

# VyxalrR, 5 3 bytes

GṖc


Try it Online!

-2 thanks to lyxal

• Try it Online! for 4 bytes Jun 24, 2021 at 7:22
• Try it Online! for 3 Jun 24, 2021 at 7:26

# Retina 0.8.2, 26 bytes

\d+
$*_ O ^ ¶ (^¶_|\1_)+$


Try it online! Takes input on separate lines but link is to test suite that splits on commas for convenience. 1-indexed. Explanation:

\d+
$*_  Convert to unary, but using a non-digit character. O  Sort. ^ ¶  Prefix a newline, so that each number is now preceded by a newline. (^¶_|\1_)+$


If at the beginning of the buffer, match a newline followed by 1 (in unary), otherwise match one more than the previous match (still with preceding newlines). If the input was a permutation then the buffer will contain an ascending sequence and the match will reach the end of the buffer.

# Wolfram Language (Mathematica), 16 bytes

PermutationListQ


Try it online!

# Pari/GP, 31 bytes

f(v)=vecsort(v)==vector(#v,i,i)


Try it online!

• v->vecsort(v)==[1..#v] Sep 29, 2021 at 11:12

# APL(Dyalog Unicode), 117 bytes SBCS

∧/⍳∘⍴∊⊢


Try it on APLgolf!

• thanks to @ovs for saving 4bytes by using a train!

Old explanation

∧/     all
(⍳⍴⍵)  [1..length]
∊⍵     belongs to input?

• You can get rid of the parentheses by commuting ∊: {∧/⍵∊⍨⍳⍴⍵}
– ovs
Jun 27, 2021 at 14:36
• and this gets a few bytes shorter as a train: razetime.github.io/APLgolf/…
– ovs
Jun 27, 2021 at 14:41
• @ovs thanks, I still find hard to understand it though.. Trains are so big! Jun 28, 2021 at 10:05
• The tree representation might help you read the train, and a few links in increasing order of detail that helped me: 1 2 3. Trains are definitely one of the more difficult things in learning Dyalog APL.
– ovs
Jun 28, 2021 at 10:28

# C (gcc), 64 bytes

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


Try it online!

# jq, 20 bytes

[range(max)+1]==sort


Try it online!

## Explanation

       max            # Get the maximum of the input
range(   )           # Generate the non-negative integers below that
+1         # Add 1 to each of them
[            ]        # Collect as list
sort  # Sort the input list
==      # Compare the two lists


# BQN, 4 bytesSBCS

∧≡⊒˜


Run online!

Uses this tip.

# GAP, 24 bytes

p:=l->PermList(l)<>fail;


Try it online!

This is a little trick since PermList fails if l is not a permutation of 1...length(l). However, due to technical reasons this is actually a boolean value. From the GAP documentation:

fail is simply an object that is different from every other object than itself.

For technical reasons, fail is a boolean value. But note that fail cannot be used to form boolean expressions with and, or, and not

The operator <> tests for inequality.

# TI-Basic, 17 bytes

Prompt A
SortA(ʟA
min(ʟA=cumSum(1 or ʟA


# Thunno-, $$\ 8 \log_{256}(96)\approx \$$ 6.58 bytes

Iz:DLRA=


Attempt This Online!

Input as each number on its own line.

#### Explanation

Iz:DLRA= # Implicit input. - flag subtracts one.
Iz:      # All inputs, sorted
DLR   # Duplicate and push the length range
A= # Are equal?
# Implicit output


# Desmos, 54 39 bytes

f(l)=0^{(l.sort-[1...l.total])^2.total}


Test on function f. Returns 1 if truthy, 0 if falsey.

To be honest, I thought that the solution would be shorter than this :|. Could most likely be golfed though, with a different strategy than mines.

Ok well I got much better at golfing in Desmos since 2021 and all I can say is that there are some pretty glaring byte saves in my previous version.

Try It On Desmos!

Try It On Desmos! - Prettified

# GolfScript, 6 bytes

~.,,-!
~      # parse the input string as an array
.,,   # create an array [0 1 2...] of the same length as the input
-  # get the set difference of this array and the original
! # convert the empty/non-empty array into a 1 or 0


Try It Online!

<≡⍳∘⍴


Try it online!

 ≡       - Check equality between ...
<        - ... the input vector ...
⍳∘     - ... and 1 through ...
⍴     - ... the length of the input vector.



# Arturo, 22 bytes

\$[a][=sort a 1..max a]


Try it

Checks whether the input sorted is equal to $$\[1..\mathrm{max}(input)]\$$.

# vemf, 8 bytes

{α~↨≡│α≤


## Explained

{α~↨≡│α≤
{        # Monadic function that checks if
α≤ # the sorted input
≡    # equals
α~↨     # range(1, len(input) + 1)