## One-Swappable Array

### July 24, 2015

The simplest answer is to sort and count the swaps, but that violates the O(*n*) constraint.

Our algorithm first indexes through the array from the left to find the leftmost out-of-order integer, then indexes through the array from the right to find the rightmost out-of-order integer, swaps them, then checks that the middle of the array is sorted; we return a list containing the indexes of the two integers to be swapped, or `#f`

if there is no solution:

(define (swappable? xs) (define (x i) (vector-ref xs i)) (define (swap! i j) (let ((t (vector-ref xs i))) (vector-set! xs i (vector-ref xs j)) (vector-set! xs j t))) (define (sorted? i j) (cond ((= i j) #t) ((not (< (x i) (x (+ i 1)))) #f) (else (sorted? (+ i 1) j)))) (let* ((len (vector-length xs)) (left (let loop ((i 0)) (if (= i (- len 1)) #f (if (< (x (+ i 1)) (x i)) i (loop (+ i 1)))))) (right (let loop ((j (- len 1))) (if (= j 1) #f (if (< (x j) (x (- j 1))) j (loop (- j 1))))))) (if (not (and left right)) #f (begin (swap! left right) (if (sorted? (max (- left 1) 0) (min (+ right 1) (- len 1))) (list left right) #f)))))

The hard part is making sure that we’ve dealt with all of the corner cases. What if the array is already sorted, so there is no leftmost out-of-order integer? What if the first or last integer is one of the two out-of-order integers? What if the two out-of-order integers are adjacent? Here are some test cases:

`> (swappable? '#(1 2 6 4 5 3 7))`

(2 5)

> (swappable? '#(7 6 5 4 3 2 1))

#f

> (swappable? '#(1 2 3 4 5 6 7))

#f

> (swappable? '#(7 2 3 4 5 6 1))

(0 6)

> (swappable? '#(1 2 4 3 5 6 7))

(2 3)

> (swappable? '#(2 7 3 4 5 1 6))

#f

You can run the program at http://ideone.com/YvssYR.

In Python.

Objection to the modification of the input array. This was supposed to be only a test.

I convinced myself that there have to be one or two pairs of adjacent numbers that are out of order, and those need to be compared to the numbers that are adjacent to them. To manage the complexity, I created a sort of a generator object, and a filter on it, and requested the first, second, and third such quadruple (a quadruple false when not available). Then the test was easy to write. Three linear scans over the input (two of them to find min and max), constant space for state in the generator, and multiple values should be passed without heap allocation in a quality implementation.

Today I’m telling the sourcecode processor that Scheme is “delphi”.

I tested with the following.

I got the following response.

Oops, I noticed that my derangements filter creates a new short-lived procedure for each window. That may or may not violate the constant-space requirement. I prefer to think it doesn’t, as that memory is immediately reclaimable.

Python solution.

Scan the list to find indexes where the items are out of order. If there are only two, check to see if swapping the two items would place the list in order. Special case if one of the items is first or last in the list.

My solution had a bug: two element arrays that are one-swappable are not handled correctly..

Here is a solution with at least one less bug.

Mike, your index takes O(n) space. Consider a reversed range, for example.

Use a generator expression instead of the list comprehension and only request up to one too many index elements. I haven’t exactly tested the following.

Also, there can be only one index element whenever the swapped integers are adjacent in the list.

A shorter version in Python. Basically the same as my first version, but here generators are used are used for looping. For testing I started to use hypothesis, which makes it easy to generate a lot of test cases. I think I like it.

New and improved:

[…] One-swap sorting problem in common lisp. […]