Is an Array a permutation?

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

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.

The rest of the Explanation is available for subscribers.

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Scala Concepts & Hints

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

Read more

Algorithm in Scala

4 lines of Scala (version 2.13), showing how concise Scala can be!

This solution is available for access!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Test cases in Scala

assert(isAPermutation(Array(1, 2)))
assert(!isAPermutation(Array(2)))
assert(isAPermutation(Array(2, 3, 4, 1)))
assert(!isAPermutation(Array(4, 1, 2)))
assert(!isAPermutation(Array(1, 2, 3, 3)))
def isAPermutation(a: Array[Int]): Boolean = ???