# 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? Commented 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
Commented 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. Commented 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. Commented Jun 24, 2021 at 9:13
• Would outputting 0 for one result or any other integer for the other be acceptable? Commented Jun 24, 2021 at 14:03

# 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
Commented May 13, 2023 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.] Commented May 14, 2023 at 8:00

[≡ $(+ 1)∘⍳∘⍴ ⊼]  Determines whether the sorted vector is equal to the range [1, length(input)]. Attempt This Online! # Kamilalisp, 24 bytes [≡ #0 ⍋@⍋]@$(^- 1)


A port of the APL answer.

Attempt This Online!

# C (clang), 47 bytes

Input is a null-terminated array of positive integers

i;f(*a){return!a[i++]?i=0,1:!wcschr(a,i)<f(a);}


Try it online!

# C (gcc)-m32, 35 bytes

Requires that you also pass the length

f(a,n){n=!n||wcschr(a,n)*f(a,n-1);}


Try it online!

# Scala 3, 36 30 bytes

l=>l.toSet==(1to l.size).toSet


Attempt This 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)]\$$.