# 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

# C (gcc), 95 73 72 bytes

r,t,i,j;f(a,n)int*a;{for(r=i=n;i--;r*=!t)for(t=j=n;j--;)t*=i!=a[j];n=r;}


Try it online!

Inputs a pointer to an array $$\a\$$ of zero-based integers and its length $$\n\$$ (since C pointers to arrays carry no length information).
Returns a truthy value if all $$\0\dots (n-1)\$$ integers are present or a falsey value otherwise.

### Explanation

Goes through all the numbers $$\0\dots (n-1)\$$ (in reverse order) and tests to see if they're in $$\a\$$.

Saved a whopping 19 bytes thanks to AZTECCO!!!

• @AZTECCO Figured out how to golf it with t=j=n, for some reason (overflow/underflow I'm guessing) couldn't get this to work with t*=i-a[j]. Jun 25, 2021 at 12:15
• Great! Idk.. It worked for me Jun 25, 2021 at 12:28
• @AZTECCO It fails on the second to last test. Have gone through it and t flips to $0$ without i-a[j]==0 while the code is testing for the presence of 41 (which isn't there). Jun 25, 2021 at 12:29

# 05AB1E, 3 bytes

{āQ


Try it online!

{āQ  # full program
Q  # is...
ā   # implicit input...
{    # sorted...
Q  # equal to...
ā   # [1, 2, 3, ..., length of...
# implicit input...
{    # sorted...
ā   # ]...
Q  # ?
# implicit output


# 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


# Husk, 3 bytes

-ŀ¹


Try it online!

What's left after removing (-) 1..length_of_input (ŀ¹) from the input?
Empty list = falsy (so input is permutation of 1..n); Non-empty list = truthy (input is not permutation of 1..n).

# 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
)
)

• This is not Rosetta Stone May 14 at 13:07

# Vyxal, 2 bytes

ż⊍


Try it Online!

Uses inverted truthiness (non-empty array for falsy, empty array for truthy)

This follows Vyxal's truthiness conventions, which can be checked using a boolify: Verify all test cases online! (boolified and logical NOT applied).

ż  # length range
⊍ # setwise difference


# Thunno 2, 2 bytes

ėṗ


Output with inverted booleans (allowed by community consensus). Add the ! flag if you want 1 for truthy and 0 for falsy.

#### Explanation

ė   # Length range
ṗ  # Set difference


#### Screenshot

• Is the bytecount correct? It looks like 2 to me May 11 at 19:31
• @emirps thanks for pointing it out. Either it was a typo or I genuinely can't count :p May 12 at 6:22

# Nekomata + -e, 3 bytes

x↕=


Attempt This Online!

Inputs are 0-indexed.

x↕=
↕    Find a permutation of
x     the range from 0 to the length of the input minus 1
=   that is equal to the input


The -e flag prints True if there is a solution, and False otherwise.

# 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

# 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!

# 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!

# 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

# vemf, 8 bytes

{α~↨≡│α≤


## Explained

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

• -2 bytes using a fork: └│~↨≡≤ Apr 4 at 14:41

# Stax, 4 bytes

àæ↓Δ


Run and debug it

This is Packed Stax which unpacks to the following 5 bytes:

%Rx-!


Run and debug it

 R    # range 1..
%     # input length
x-  # setwise difference with register x (which is set to the input by default)
! # logical NOT

• I don’t speak Stax. As swapping truthy and falsy is allowed, do you still need !?
– tsh
Apr 4 at 0:18
• @tsh I only used the logical NOT because the setwise difference returns an empty array for truthy and a non-empty array for falsy. If those two values are allowed to be used then it would be able to be removed. Apr 4 at 2:31

# PARI/GP, 66 bytes

Try it online!

f(a)={for(i=1,#a,if(setsearch(Set(a),i)==0,return(0)));return(1);}


# Vyxal, 12 bytes

?£(|)1¥G›r¥⁼


Try it Online!

• Did you mean to keep the (|)? It technically doesn't do anything. Try it Online! for 9 bytes without it or Try it Online! for 8.5 bytes using vyncode May 1 at 22:11

# APL(Dyalog Unicode), 5 bytes SBCS

^/⍋∊⊢


Try it on APLgolf!

A tacit function that returns if every number from 1..n is in the array.

## Explanation

^/⍋∊⊢
^/    all
⍋   (a permutation of) numbers from 1..n
∊  are members of
⊢ the array


# Lua, 64 bytes

load't=...table.sort(t)for i=1,#t do b=b or i~=t[i]end return b'


Try it online!

Truthy and falsy values are swapped.

## Pascal, 134 Bytes

This function requires a processor supporting Extended Pascal as defined by ISO standard 10206 (level 1).

type Z=integer;function f(A:array[p..q:Z]of Z):Boolean;var S:set of Z;i:Z;begin S:=[];for i:=p to q do S:=S+[A[i]];f:=S=[1..q-p+1]end;


Ungolfed:

function f(A: array[minimum..maximum: integer] of integer): Boolean;
var
members: set of integer value [];
i: integer;
begin
{ transform an ordered array into an unordered set }
for i := minimum to maximum do
begin
{ form the union of two sets }
members := members + [A[i]]
end;
{ analyze: compare members to a set of [1..n] }
f := members = [1..(maximum - minimum + 1)]
end;


Evidently, the implementation is index-insensitive.

• Will convert return type to Z save some bytes?
– tsh
May 13 at 23:39
• @tsh No, only one Byte. You will then need to use the conversion function ord() to convert the final Boolean result expression into an integer value. [Besides 0 and 1 are not truthy/falsy values in Pascal, only true and false are.] May 14 at 8:00