Is this a Permutation of 1..n

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

Japt, 4 3 bytes

0-based

Íe¶

Try it or run all test cases

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

Answer 7

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 / Python^regex / .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)
        .*     # Skip to anywhere in the string, putting it in head
    )
)

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), _³⁶ 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
    (?=               # Lookahead
        .*            # 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+), _⁴¹ 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+}}), _⁴⁴ 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
    )
)

Answer 8

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

Answer 9

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

Answer 10

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.

Answer 11

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

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

Try it online!

Answer 12

Vyxal rR, 5 3 bytes

GṖc

Try it Online!

-2 thanks to lyxal

Answer 13

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.

Answer 14

Wolfram Language (Mathematica), 16 bytes

PermutationListQ

Try it online!

Answer 15

Pari/GP, 31 bytes

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

Try it online!

Answer 16

APL(Dyalog Unicode), ¹¹7 bytes ^SBCS

∧/⍳∘⍴∊⊢

Try it on APLgolf!

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

Old explanation

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

Answer 17

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!

Answer 18

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!

Answer 19

BQN, 4 bytes^SBCS

∧≡⊒˜

Run online!

Uses this tip.

Answer 20

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.

Answer 21

TI-Basic, 17 bytes

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

Answer 22

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 

Answer 23

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

Answer 24

vemf, 8 bytes

{α~↨≡│α≤

Explained

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

Answer 25

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

Answer 26

PARI/GP, 66 bytes

Try it online!

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

Answer 27

Vyxal, 12 bytes

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

Try it Online!

Answer 28

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

Answer 29

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.

Answer 30

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.