Task — Semi-ordered permutation

You are given permutation of $n integers, @ints. Write a script to find the minimum number of swaps needed to make the @ints a semi-ordered permutation. A permutation is a sequence of integers from 1 to n of length n containing each number exactly once. A permutation is called semi-ordered if the first number is 1 and the last number equals n. You are ONLY allowed to pick adjacent elements and swap them.

Examples

Example 1
Input: @ints = (2, 1, 4, 3)
Output: 2
Swap 2 <=> 1 => (1, 2, 4, 3)
Swap 4 <=> 3 => (1, 2, 3, 4)

Example 2
Input: @ints = (2, 4, 1, 3)
Output: 3
Swap 4 <=> 1 => (2, 1, 4, 3)
Swap 2 <=> 1 => (1, 2, 4, 3)
Swap 4 <=> 3 => (1, 2, 3, 4)

Example 3
Input: @ints = (1, 3, 2, 4, 5)
Output: 0
Already a semi-ordered permutation.

Analysis

This gives the answer:

• Find the index (s) of the smallest and (b) the biggest integers
• Add s and n - b - 1
• Subtract 1 if s > b

Why does this work?

Start by remembering that the array is zero based, so the indices run from 0 to z where z = $n - 1.

Consider the case when the smallest integer is to the left of (ie has a lower index than) the biggest. The quickest way to get it to index 0 is to swap it successively with the integers on its left - which will take s swaps to get it to index 0.

Similarly, we can swap the largest successively with the integer on its right until it gets to the end, which will take z - b swaps.

So the minimum number of swaps to achieve semi-order is s + z - b.

But what about the case where the smallest integer starts to the right of the largest?

The numbers of swaps for the smaller and for the larger number are unchanged, but one of these swaps is when these two numbers swap with each other, so the total number of swaps is one fewer:
s + z - b - 1.

And that's my solution.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-11-25
use utf8;     # Week 297 - task 2 - Semi-ordered permutation
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

semiordered_permutation(2, 4, 6, 8, 1, 3, 5, 7);
semiordered_permutation(7, 5, 3, 1, 8, 6, 4, 2);
semiordered_permutation(1, 2, 3, 4, 5, 6, 7, 8);
semiordered_permutation(8, 7, 6, 5, 4, 3, 2, 1);

sub semiordered_permutation {
    
    my (@ints, $z, $smallest, $largest, $j, $smallest_j, $largest_j, $swaps);
    
    # find the indices of smallest and largest integers
    @ints = @_;
    $smallest = 1e6;
    $largest = -1e6;
    $z = @ints - 1;
    for $j (0 .. $z) {
        if ($ints[$j] < $smallest) {
            $smallest = $ints[$j];
            $smallest_j = $j;
        }
        if ($ints[$j] > $largest) {
            $largest = $ints[$j];
            $largest_j = $j;
        }
    }
    
    # calculate answer (see blog)
    $swaps = $smallest_j + $z - $largest_j;
    $swaps -= 1 if $smallest_j > $largest_j;
    
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    say qq[Output: $swaps];
}

Output

Input:  @ints = (2, 4, 6, 8, 1, 3, 5, 7)
Output: 7

Input:  @ints = (7, 5, 3, 1, 8, 6, 4, 2)
Output: 6

Input:  @ints = (1, 2, 3, 4, 5, 6, 7, 8)
Output: 0

Input:  @ints = (8, 7, 6, 5, 4, 3, 2, 1)
Output: 13