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

Risky, 7 bytes 7 bytes and a palindrome

1_??!0:0!??_1


Try it online!

Explanation

1   sort
_
?         input
?     filter by
!       factorial
0         0
: =
0   range
!       length
?         input
?     find first number such that
_
1         1


J, 7 bytes

-:/:@/:


Try it online!

Ninja'd by hyper-neutrino :(

Takes zero-based input. Applying Grade Up twice to a vector gives a "ranking" of each element, so that 0 is the smallest, 1 is the next smallest, ... up to n-1, breaking ties by giving a smaller number to the one appearing first. A vector is a permutation if and only if the ranking is identical to itself.

J, 7 bytes

2|C.!.2


Try it online!

Takes zero-based input. C.!.2 is a built-in for "cycle parity". It gives 1 if a permutation has even number of swaps, -1 if odd, and 0 if not a valid permutation. I take it modulo 2 to convert all nonzero results to 1 (the only truthy value in J).

Even if error/non-error output were allowed, it is too bad that permutation-related built-ins A. and C. don't error on all possible non-permutations.

J, 7 bytes

#\-:/:~


Try it online!

Takes one-based input. #\ is a golfing trick for getting 1..n, which is compared to the sorted array /:~ of the original.

If output by erroring/non-erroring is allowed:

J, 3 bytes

C.~


Try it online!

Takes zero-based input. Abuses dyadic form of C., whose left argument must strictly be a permutation. It throws an index error otherwise.

APL (Dyalog Unicode), 5 bytes

⊢≡⍋∘⍋


Try it online!

-4 bytes thanks to Bubbler by turning this into a train and via using ⍵≡ to match the whole array instead of ∧/⍵= to match element-wise and then reduce by AND.

⊢≡⍋∘⍋    Train
≡         Check equality between
⊢         (Right argument ⍵) and
⍋∘⍋    Composed function {⍋⍋⍵}; grade up twice


Grading up twice gives the minimum permutation of length X that has the same (non-strict) ordering as the original - so, if the permutation of the right order is the same as the original, then the original was that permutation and thus a permutation.

• You can delete ∧/ and change = (element-wise equals) to ≡ (entire array match). The train version is ⊢≡⍋∘⍋. Commented Jun 24, 2021 at 6:39
• @Bubbler Ah, I should've looked for that built-in instead of using ∧/= :P thanks! Commented Jun 24, 2021 at 6:40
• May I use this for APLcart? (This entails relinquishing all rights to the code.)
Commented Jun 24, 2021 at 7:01
• @Adám Sure, that's cool with me and I checked with Bubbler too :) Commented Jun 24, 2021 at 14:54

Courtesy of AZTECCO

g l=all(eleml)[1..length l]


Try it online!

Haskell (0 indexed), 4232 31 bytes

Lynn saved one byte with the pointfree solution.

all.(.fst).flip elem<*>zip[0..]


Try it online!

I tried a bunch of creative stuff with scans, folds and zips, but the boring solution ended up being the shortest.

Both of these check that every integer in the available range is in the list. The first is 1 to the length of the list, the second is 0 to 1 less than the length of the list.

• There's a shorter solution without import :)
– xnor
Commented Jun 24, 2021 at 12:58
• @xnor Ah indeed. And much shorter. Commented Jun 24, 2021 at 13:04
• With sorting, this pointfree saves a byte, using flipped output: Try it online!
– xnor
Commented Jun 24, 2021 at 13:07
• Looks like all.(.fst).flip elem<*>zip[0..] is a hair shorter.
– lynn
Commented Jun 24, 2021 at 16:37
• If I'm not missing something..Try it online! Commented Jun 24, 2021 at 17:55

Python 3, 31 bytes

Input is $$\ 0 \$$-indexed.

lambda a:{*a}=={*range(len(a))}


Try it online!

This is the most obvious implementation I could think of. It compares the set of $$\ a \$$ to the set of numbers from 0 to len(a)-1.

Python 3, 30 bytes

As @ovs suggested, we can save a byte by switching the definition of truthy and falsey. A valid permutation returns a falsey value, and truthy otherwise.

lambda a:{*a}^{*range(len(a))}


Try it online!

• If you swap truthy and falsy outputs (as allowed in the post), the == can be a ^.
– ovs
Commented Jun 24, 2021 at 8:12
• This answer is old, but I am pretty sure this would fail for many inputs with duplicated values, e.g [1,2,1] Commented Apr 16, 2022 at 4:17
• @des54321 It does? I think it correctly identifies [1,2,1] as False. Commented Apr 16, 2022 at 5:03
• @dingledooper never mind actually, youre correct, my mental analysis missed that the len(a) bit handled checking for non-unique values in the input Commented Apr 16, 2022 at 5:08

JavaScript (ES6), 30 bytes

Expects 0-indexed values. Returns a Boolean value.

a=>a.every(x=>(a[~x]^=1)/a[x])


Try it online!

Commented

We test whether all values are less than the length $$\N\$$ of the input array and make sure that there is no duplicate. Both conditions are satisfied iff the array consists of all values from $$\0\$$ to $$\N-1\$$.

a =>             // a[] = input array
a.every(x =>   // For each value x in a[]:
(a[~x] ^= 1) //   ~x is -x - 1, which is guaranteed to be negative
//   Therefore, a[~x] is a property (such as '-1') of
//   the underlying object of a[], which can be safely
//   used to store values that were already encountered
//   If a[~x] XOR 1 is not equal to 1, we have a
//   duplicate value
/ a[x]       //   We also make sure that a[x] is defined, which
//   means that x < a.length
//   The possible cases are:
//     1 / n, n > 0 is a truthy number  \__ success
//     1 / 0 is +Infinity (also truthy) /
//     1 / undefined is NaN (falsy)     \
//     0 / n, n > 0 is 0 (falsy)         |_ failed
//     0 / 0 is NaN (falsy)              |
//     0 / undefined is NaN (falsy)     /
)              // End of every()


Julia 1.5, 6 bytes

This is a built-in, so it's quite easy for Julia

isperm


Use it like this: isperm([6,3,8,12,1,10,4,2,7,9,5,11])

• That's almost Mathematica-level surprising!
– ojdo
Commented Jun 25, 2021 at 8:22

Zsh, 18 12 11 bytes

>$@<{1..$#}

Attempt This Online!

Outputs via exit code: 0 for a permutation and 1 for not a permutation

Explanation:

• >: create files called
• $@: each command-line argument • {1..$#}: range from 1 to the number of command-line arguments
• <: try to read from each of those numbers as a file

If any command fails, then that means one of the files in the range didn't exist, so it's not a valid permutation, and zsh will exit with status 1.

R, 26 24 bytes

-2 bytes thanks to pajonk.

all(seq(x<-scan())%in%x)


Try it online!

If input is of length at least 2, seq(x) outputs the integers from 1 to length(x); if input is of length 1, it outputs the integers from 1 to x. Return TRUE iff all those integers are elements of x.

• I don't think the ! is necessary here. Commented Jun 24, 2021 at 7:58
• @pajonk Indeed, thanks! Commented Jun 24, 2021 at 8:01
• And now we can do all(seq(x<-scan())%in%x) Commented Jun 24, 2021 at 8:02

Ruby, 21 bytes

->a{a|[*1..a.max]==a}


Try it online!

-1 byte thanks to ovs!

-3 bytes thanks to Razetime!

• I'm not completely sure, but ->a{a|[*1..a.max]==a} might work.
– ovs
Commented Jun 24, 2021 at 8:19
• @ovs seems to be working!
– user100752
Commented Jun 24, 2021 at 8:20

Python 3, 33 bytes

lambda x:max(*x,len(x))^len({*x})

1. Check uniqueness: len(x) = len(set(x))
2. For unique set: max(x) == len(x) iff x = 1...n

Try it online!

Factor + math.unicode, 24 23 bytes

[ dup length iota ⊃ ]


Try it online!

0-indexed to save a byte. Is the input a superset of $$\[0..|input|)\$$?

Zsh, 13 bytes

: >$@<{1..$#}


Try it online!

:              noop command to prevent hanging while waiting for input
>$@ create a file for every argument <{1..$#}  read every file between 1 and the number of arguments


Since the redirects are handled left-to-right, we create the files before trying to read them. If we encounter a number for which no file exists (for example on zsh x.zsh 4 1 2), we get the following error:

no such file or directory: 3

and receive exit code 1. If it was indeed a permutation, we exit cleanly with code 0.

• Welcome to Code Golf, and nice first answer! I've edited your answer slightly to include a link to Try it online! so that others can test your solution. Don't worry about not being able to comment, we encourage new users to post solutions, even if they're golfs of current ones :) Commented Jun 25, 2021 at 12:16

BitCycle-u, 91 bytes

v 0< <  <
ABv
^/=^?^
v<
Hvv <<
/<CDv
!v /=^
v  =\\\v
~~< >+
<@>G^
>E\^
>~> \/
> F//@


Outputs 1 for truthy, 0 for falsey. Try it here!

Explanation

The algorithm is as follows:

• Loop until the list is empty:
1. Decrement every number in the list
2. If there is not exactly one zero in the list, halt and output 0
3. Otherwise, remove the zero from the list and continue
• If the loop ran to completion, output 1

The program contains two main sections, one that accomplishes step 1 and one that accomplishes steps 2 and 3. Here they are as separate programs:

Step 1

?0 v
v  <
ABv
^/=^
C\!


Subtracts 1 from every number in the list. Try it!

We prefix a 0 bit to the input so every unary number has a leading 0. Each time through the A-B loop, we use the first bit to set the switch (=) and then send it into the C collector.

• If the first bit was 0, the rest of the bits go west. We use the splitter / to discard the second bit and sent the rest of the bits back into A. The second bit is guaranteed to be 1, since all the numbers in the list are positive.
• If the first bit was 1, the rest of the bits go east, right back into A.

The upshot is that one bit from each of the unary numbers gets discarded, subtracting 1 from each of them.

Steps 2-3

?0v  <
CDv
v /=^
v  =\\\v
~~< >+
< >G\!
>E\^@
>~> \/
> F//@


Halts if there are no zeros or multiple zeros in the list, otherwise filters the zero(s) out of the list. Try it!

We once again prefix a 0 bit to the input. (In the actual program, this only needs to be done once.) Each time through the C-D loop, we use the first bit to set the northeast switch (=).

• If the first bit was 1, the rest of the bits go east, right back into C.
• If the first bit was 0, the rest of the bits go west. We peel off the second bit and use it to set the southwest switch. Then we send it through the eastern dupneg (~), from which a negated copy goes into the E collector and the original copy goes back into C. The rest of the bits go through both dupnegs; a negated copy goes into E, and a doubly negated copy goes back into C.

The upshot is that all the bits after the first go back into C unchanged, but if the first bit was 0, the second bit sets the southwest switch and some bits go into E.

Meanwhile, the first bit goes through this structure:

 =
=\\\v
>+
>G


Starting from the northeast switch moving south, it bounces off the westernmost two splitters (\) and is sent to the branch (+). If it is 1, it turns right and goes into the G collector. If it is 0, it turns left, bounces off the easternmost splitter, passes back through the other two splitters, and reaches the southwestern switch.

• If the second bit was 1, the switch sends the first bit back eastward, through all the splitters, and into the G collector.
• If the second bit was 0, the switch sends the first bit westward; it eventually reaches a dupneg, from which one copy goes into the E collector and one into F.
• If there was no second bit, the inactive switch passes the first bit straight through, which behaves the same as the 0 case.

The upshot is that G gets the same list but without any 0 bit that is followed by another 0 bit or the end of the string. Also, F gets a bit for each of the 0 bits that didn't go into G, and E is guaranteed to have at least one bit in it.

Next, the E collector opens, dumps its first bit into F, and discards the rest. F now contains one bit if there were no zeros in the list, two bits if there was exactly one zero, and more than two if there were multiple zeros.

The bits from the F collector then go through this structure:

   @
> \/
F//@

• If there are more than two bits, the first two bounce off the splitters on the bottom row, allowing the third one to pass through both splitters and hit the southeastern halt instruction (@).
• If there are two bits, the first one bounces off the westernmost two splitters and goes west. Meanwhile, the second one bounces off the easternmost two splitters and goes east off the playfield. The first bit is sent back east, goes through the two northernmost splitters, and off the playfield.
• If there is one bit, it bounces off the westernmost splitters, turns around, bounces off the northeastern splitter, and hits the northern halt instruction (@).

The upshot is that if there was not exactly one zero in the list, the program halts. No bits have been output yet, which with the -u flag means the output is 0. If there was exactly one zero, the program does not halt; the G collector opens and the program continues.

Tying it together

In the full program, the output from the G collector is sent back into A, starting the loop over again.

Meanwhile, the discarded 1 bits from step 1 have been collected in H. Once there are no bits left in the main loop, H opens. The splitter (/) sends its first bit into the sink (!), outputting 1. The rest of the bits go through the splitter and off the playfield.

Jelly, 3 bytes

Ṣ⁼J


Try it online!

Ṣ⁼J   Monadic Link
Ṣ     1-chain: sort the input
⁼J   2,1-chain: is (the input sorted) equal to (range on the length of the input)?


Brachylog, 3 bytes

o~⟦


Try it online!

0-indexed. Succeeds or fails.

o      The input sorted
~⟦    is the range from 0 to something inclusive.


Note that this can not be golfed to ⟦p with reversed input, as it fails to terminate for cases it should reject:

⟦     Choose an integer. Is the range from 0 to it inclusive
p    a permutation of the input?


Pyth, 3 bytes

UIS


Try it online!

• Wow... I had a 6 byter, had no idea U had that use. Nice! Commented Jun 24, 2021 at 17:19

R, 27 bytes

any(rank(x<-scan(),,'f')-x)


Try it online!

Returns FALSE for Truthy, TRUE for FALSY (just to shave one byte)

Explanation:

If the array containing the rank of each value is equal to the input array, then it's a permutation of 1..n

Note:
5 bytes are wasted because in rank function the default handling strategy in case of ties is "average their ranks" instead of any of the other possibilities... argh!

• -1: any(rank(x<-scan())-x) swapping thruthy and falsy. (TIO link too long for the comment) Commented Jun 24, 2021 at 7:54
• @pajonk: I was just changing it while you were posting your comment ! :D Commented Jun 24, 2021 at 7:55
• I think this fails on input 1,3,3,3,5. Commented Jun 24, 2021 at 7:57
• @RobinRyder: you're right... damn, I always forget that rank default for ties is avg... Commented Jun 24, 2021 at 8:02

Perl 5, 38 bytes

sub{!grep!{map+($_,1),@_}->{$_},1..@_}


Try it online!

• 28 bytes using full program Commented Jun 24, 2021 at 11:55
• @NahuelFouilleul - Nice. Commented Jun 25, 2021 at 11:23

Red, 46 bytes

func[a][i: 0 until[alter a i: 1 + i]single? a]


Try it online!

increments a counter as long as the counter is found in the list, and then checks it against the length.

1 = length? is used as a polyfill for single? in the latest Red version.

-5 bytes from tsh.

-5 bytes from Galen Ivanov.

• Maybe i >(length? a)?
– tsh
Commented Jun 24, 2021 at 7:00
• yes, it works. Thanks. Commented Jun 24, 2021 at 7:16
• Once again, alter (plus reversal of logic) helps to get rid of 5 bytes: func[a][i: 0 until[alter a i: 1 + i]single? a]. (single? doesn't work in TIO, must be replaced by 1 = lenght? a) Commented Jun 24, 2021 at 18:18
• only one more answer for an alter hattrick :P Commented Jun 25, 2021 at 3:46
• @Razetime haha, yes! Commented Jun 25, 2021 at 6:42

Java (JDK), 43 bytes

a->a.sorted().reduce(1,(x,y)->y==x?x+1:0)>0


Try it online!

Explanations

This answer is a Predicate<IntStream> and requires that the input contains no 0.

First this code sorts the input stream. The reduce method then makes sure that each consecutive number is encountered, and return the last encountered number. x always contains the next expected number, or 0 if we got an unexpected number. 1 is the first parameter of the reduce method as it's the first expected number. Given that 0, or any negative number, is not allowed in the IntStream, when 0 is returned for the first time, it will always be returned for the remaining of the process.

TypeScript's Type System, 450 442 bytes

type A<T extends any[]>=T extends{length:infer L}?(L extends number?L:never):never
type B<L extends number,T extends 0[]=[]>=T extends{length:L}?T:B<L,[...T,0]>
type C<N extends number,T extends number=1,R extends any[] = []> = R['length']extends N?R:C<N,A<[...B<T>,0]>,[...R,T]>
type D<T extends any[],U extends any[]>=T extends[]?true:T extends[infer H,...infer R]?H extends U[number]?D<R,U>:false:never
type F<T extends any[]>=D<T,C<A<T>>>


Explanation

// This allows getting the Length of any tuple via inferring its L property
type A<T extends any[]>=T extends{length:infer L}?(L extends number?L:never):never

// This creates a tuple of arbitrary length L (we need to use this later for arithmetic)
type B<L extends number,T extends 0[]=[]>=T extends{length:L}?T:B<L,[...T,0]>

// We can use this to generate an incrementing tuple of length L (e.g. [1, 2, 3, 4]). We use this to compare against the final array.
type C<N extends number,T extends number=1,R extends any[] = []> = R['length']extends N?R:C<N,A<[...B<T>,0]>,[...R,T]>

// This checks if two arrays have the same elements inside them
type D<T extends unknown[],U extends unknown[]>=T extends[]?true:T extends[infer H,...infer R]?H extends U[number]?D<R,U>:false:never

// Finally, we can use this to compare the chosen array T vs the increasing tuple N
type F<T extends any[]>=D<T,C<A<T>>>

• A can probably just be T["length"], which can then be inlined. Commented May 12, 2023 at 11:21

Wolfram Language (Mathematica), 22 20 bytes

Sort@#==Range@Max@#&


-2 bytes, thanks to @ZaMoC:

Try it online!

• 20 bytes Commented Jun 24, 2021 at 8:22

Stax, 5 bytes

c%R|}


Run and debug it

Explanation:

     ; Implicit input onto top of stack
c    ; Copy top of stack
%    ; Length of top of stack
R    ; Make range [1 .. n]
|}   ; Compare top two elements of stack. Arrays are different orderings of same elements?
; Implicit output of truthy/falsy


Could probably save a byte somewhere.

• oc%R- exists, but i don't think there's away to get this to pack. Commented Jun 29, 2021 at 5:12

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


Nibbles, 1.5 bytes (3 nibbles)

-,,


Returns an empty list (falsy) if input is a permutation of 1..n, or a non-empty list (truthy) if it is not.

-       # remove
,      #   sequence of 1..
,     #   length of
#   (implicitly) input
# from
#   (implicitly) input


Python, 43 39 Bytes

lambda x:sorted(x)==list(range(len(x)))


0-indexed. Uses sorted(), range() and list(). Surprisingly gives correct answer for empty list.

Test on TIO.

• You can remove the space between len(x)) and for y Commented May 13, 2023 at 12:57
• You can also remove the square brackets inside all, a generator will work there, it doesn't need to be a list Commented May 13, 2023 at 12:58
• Also the answer is invalid: tio.run/##K6gsycjPM/… Returns true on many of the falsy test cases Commented May 13, 2023 at 13:00
• @mousetail fixed Commented May 14, 2023 at 8:57
• Smart solution, well done Commented May 14, 2023 at 11:08

Charcoal, 6 bytes

¬⁻Ｅθκθ


Try it online! Link is to verbose version of code. 0-indexed. Outputs a Charcoal boolean, i.e. - for permutation, nothing if not. Explanation:

   θ    Input array
Ｅ     Map over elements
κ   Current index
⁻      Remove values found in
θ  Input array
¬       Check that nothing is left
Implicitly print


(Mapping over the input indices is golfier than creating a range.)

JavaScript (Node.js), 40 38 bytes

s=>s.sort((a,b)=>a-b).some((x,i)=>x^i)


Try it online!

Returns true for invalid and false for valid. Put a ! before the s.sort for the otherway round. Takes input 0-indexed.

• 0-indexed is allowed, so you can remove ++.
– user100690
Commented Jun 24, 2021 at 7:51
• (a,b)=>a-b -> a=>b=>a-b from this tip Commented Jun 24, 2021 at 8:15
• @razetime that wont work for the sort function
– user100752
Commented Jun 24, 2021 at 8:18
• oh, too bad..... Commented Jun 24, 2021 at 8:19
• @RecursiveCo. thanks! Commented Jun 24, 2021 at 9:02

jq, 2049 36 bytes

length==max and max==(unique|length)


Try it online!

Thanks to tsh and xigoi for catching mistakes in the previous attempts...

Third time is the charm perhaps?

Since the rules limit the numbers to "positive integers", there's no need to test the minimum. Making sure the largest number in the list, the size of the original list and the size of a de-dup'd list are all the same is sufficient. So that's what this version does.

• Failed on [1,1,1]
– tsh
Commented Jun 24, 2021 at 9:25
• Re-written to actually do what the challenge called for... Commented Jun 24, 2021 at 10:10
• Maybe [1,3,3]?
– tsh
Commented Jun 24, 2021 at 10:39
• I think it should be == instead of -. Commented Jun 24, 2021 at 16:35