# Permutate elements of an array

13 Sep 2018### Problem statement

Write a function that given two arrays arguments `s`

and `p`

, returns an array with rearranged elements according to indexes specified in the array `p`

.

```
EXAMPLE:
Input: s = [9,8,7,6,5], p = [1,4,0,2,3]
Output: [8,5,9,7,6]
```

### Solution

Here is the actual code of the algorithm that implements a solution to permutate elements of an array using the specified permutation:

```
func apply(s: [Int], p: [Int]) -> [Int] {
// Validate input arguments
precondition(s.count == p.count, "Arguments must have equal length")
// Query size of the sequence
let size = s.count
// Prepare state of the algorithm
var seq = s, perm = p
// Loop thru all elements of the sequence
for i in 0..<size {
// Make a copy of the current element's position
var lhs = i
// Exchange current element unless it has been exchanged
while perm[lhs] != -1 {
// Get 2nd part of the exchange and value at the destination
let rhs = perm[lhs], rxs = perm[rhs]
// Looks like the exchange was done earlier, thus stop
if rxs == -1 { break }
// Perform exchange operation in the specified positions
swap(&seq, lhs, rhs)
// Mark the left part of current exchange as completed
perm[lhs] = -1
// Let the exchange to keep going further (eq. chain)
lhs = rhs
}
}
// Here is the answer
return seq
}
```

Following is the traditional section with assertions to validate the code performs as advertised and establish a baseline for any improvement work in the future:

### Bits & pieces

This coding challenge is one of those that look straightforward at first sight but in fact might take a little while to get the code working reliably with various inputs.

Lets get started!

The very first instruction validates input arguments to ensure expectations and constraints of the algorithm are met by the caller:

```
// Validate input arguments
precondition(s.count == p.count, "Arguments must have equal length")
```

This next instruction is a convenience shorthand to retrieve the number of elements in the original sequence. Since it is used in a few places in the code giving it a friendly name helps to aid readability:

```
// Query size of the sequence
let size = s.count
```

Following instruction creates local copies of the original sequence and permutation to make it possible change contents of both within the function (*quirk of Swift*) and that concludes state preparation of the algorithm:

```
// Prepare state of the algorithm
var seq = s, perm = p
```

This code snippet is the **main loop** to iterate over the sequence and rearrange elements as requested, though each and every permutation usually incurs a chain of subsequent permutations that follow:

```
// Loop thru all elements of the sequence
for i in 0..<size {
... inner block of code ...
}
```

This statement copies position of the current element into `lhs`

variable, which serves as a starting point of the current permutation and other permutations that follow, eq. forming a chain. That makes the algorithm to execute faster and consume less space:

```
// Make a copy of the current element's position
var lhs = i
```

Following statement is the **inner loop** to handle current permutation and permutations to chain with this one. Since the loop cannot run indefinitely, hence the exchange (*eq. permutation*) is performed only if it hasn’t been already done before (*exchanges already done are marked with -1*):

```
// Exchange current element unless it has been exchanged
while perm[lhs] != -1 {
... inner block of code ...
}
```

This statement makes a copy of the element’s position to perform the exchange with into `rhs`

variable and **lookahead** position of the element to chain the next exchange with into `rxs`

variable (*very important step and it is used to keep permutation sequence in valid state at all times*):

```
// Get 2nd part of the exchange and value at the destination
let rhs = perm[lhs], rxs = perm[rhs]
```

Next statement checks whether the exchange in the **lookahead** position has been already performed and breaks out of the loop if that is the case, without this check the subsequent exchanges in the chain would end up producing invalid results:

```
// Looks like the exchange was done earlier, thus stop
if rxs == -1 { break }
```

This statement simply performs an in-place exchange of both elements with using a helper function and there is not much else about it:

```
// Perform exchange operation in the specified positions
swap(&seq, lhs, rhs)
```

Following statement marks **left part** of exchange (*hence use of lhs variable*) as completed and leaves a mark for subsequent exchanges that this permutation is already in the desired state and can be safely ignored:

```
// Mark the left part of current exchange as completed
perm[lhs] = -1
```

Last statement of the **inner loop** copies value of `rhs`

into `lhs`

variable, effectively transforming **right part** of the exchange performed to be **left part** of the next exchange that follows, therefore making it possible to simulate behavior of the **chaining effect**:

```
// Let the exchange to keep going further (eq. chain)
lhs = rhs
```

As soon as the **main loop** is over, the function is ready to return a sequence that has its elements rearranged according to the specified permutation:

```
// Here is the answer
return seq
```

That’s all folks! ⛓

Here is a Swift playground for this article at Github: Permutate elements of an array.