# Scala algorithm: Is an Array a permutation?

Published

## Algorithm goal

A permutation of an array $$X$$ is another array of the same size, which has the same elements. $$[3,2,1],$$ is a permutation of $$[1,2,3]$$, but $$[2,1]$$ is not because $$3$$is missing.

Problem: For an array size $$N$$, check whether it is a permutation of $$[1, 2, ..., N]$$.

For example, for $$[4,3,2,1]$$, $$N = 4$$,and it is a permutation of sequence $$[1,2,3,4=N]$$.

However, for array $$[4,3,2]$$, $$N = 3$$, and $$[4,3,2]$$ is not a permutation of $$[1,2,3=N]$$.

Check whether an input is a permutation of $$(1..N)$$ where $$N$$ is the length of the input.

This problem is related to the Codility problem 'PermCheck'.

## Algorithm in Scala

4 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!

## Explanation

The solution is very small yet intricate because Scala provides very terse syntax.

Firstly, the nature of the algorithm is: the length of the array corresponds to number $$N$$. Then we need to check that each item in $$(1..N)$$ is in the array. For this we use Scala's range syntax which allows us to produce a description (not a collection) of the range (which can then be acted on as a collection if need be). (this is © from www.scala-algorithms.com)

To check each item directly in the array with .contains would be very expensive as we'd have to go through the array mutliple times, leading to $$O(n^2)$$ complexity.

## Scala concepts & Hints

1. ### Range

The (1 to n) syntax produces a "Range" which is a representation of a sequence of numbers.

assert((1 to 5).toString == "Range 1 to 5")

assert((1 to 5).reverse.toString() == "Range 5 to 1 by -1")

assert((1 to 5).toList == List(1, 2, 3, 4, 5))


# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

### Study our 89 Scala Algorithms: 6 fully free, 89 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 21 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Register now (free)

Register with GitHub

This gives you access to free test cases & hints for all our 89 published algorithms as well as our installation-free Scala IDE.

You can then choose to subscribe to "Scala Algorithms Unlimited", which gets you access to every current and upcoming algorithm solution. We use Stripe so your data is safe.

We will e-mail you at most once per week with new algorithms and relevant content.
Your data is protected and unsubscribing is straightforward.