# In Place Permutations

A cautionary tale wherein I successfully nerd-snipe^{1} myself.

It all started with an apparently simple programming question on Programming Praxis;

Given an array consisting of 2n elements in the form [x1,x2,…,xn,y1,y2,…,yn], return the array in the form [x1,y1,x2,y2,…,xn,yn].

…and to do it in Scheme with `list-ref`

and `length`

.

That's not too hard: I can imaging successively `cons`

-ing the right
values onto a list recursively and then reversing it:

(define (shuffle xs) (reverse (shuffle-helper xs (/ (length xs) 2) 0 '()))) (define (shuffle-helper xs n i ys) (if (>= i n) ys (let ((a (list-ref xs i)) (b (list-ref xs (+ n i)))) (shuffle-helper xs n (+ 1 i) (cons b (cons a ys)))))) (display (shuffle '(1 2 3 4 a b c d)))

(1 a 2 b 3 c 4 d)

That said, `list-ref`

will be linear so I'm not sure I like this
solution very much. If I was doing it without these constraints, I'd
prefer to do it by splitting the list first, and then `cons`

-ing things
together.

(define (drop ls n) (if (= 0 n) ls (drop (cdr ls) (- n 1)))) (define (shuffle2 ls) (letrec ((n (/ (length ls) 2)) (ys (drop ls n))) (reverse (shuffle2-helper ls ys '())))) (define (shuffle2-helper xs ys result) (if (or (nil? xs) (nil? ys)) result (shuffle2-helper (cdr xs) (cdr ys) (cons (car ys) (cons (car xs) result))))) (display (shuffle2 '(1 2 3 4 a b c d)))

(1 a 2 b 3 c 4 d)

As pleasant as these excursions might have been while writing this
note, this was *not* the rabbit hole I fell down a few days ago. You
see, I've been getting back into Rust again^{2}.

The direct solution in Rust is fairly convenient: allocate a linear
amount of memory, fill in the array, and we're done. Of course,
there's another interesting detour here that I'll return to *after*
talking about the *first* rabbit hole I fell into.

fn shuffle3<T: Copy>(vec: &mut [T]) { let duplicate: Vec<T> = vec.to_vec(); let n = vec.len() / 2; for (i, e) in duplicate.iter().enumerate() { if i < n { vec[i * 2] = *e; } else { vec[(i - n) * 2 + 1] = *e; } } } fn main() { let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8]; shuffle3(&mut vec); println!("{:?}", vec) }

[1, 5, 2, 6, 3, 7, 4, 8]

I started wondering if there was a way to do this *without* using
memory, and still using linear time.

It *should* be feasible to shuffle the array with swaps: and I can
deterministically calculate the cycles. The main problem is that I
can't save *which* cycles have been visited, which makes this linear in
size again.

My first attempt at solving this was to start *pulling* values into the
right places from left to right: if I'm pulling in a number from
*beyond* the current point, I simply swap. If I'm pulling in a number
from *before* the current point, the original number has already been
swapped – potentially several times.

This ends up making the solution super-linear in time complexity, but
I haven't yet managed to find the estimate the actual complexity. If I
consider *any* arbitrary permutation, then the time complexity becomes
`O(n^2)`

in the worst case.

fn from(x: usize, n: usize) -> usize { if x & 1 == 0 { x / 2 } else { n + (x - 1) / 2 } } fn shuffle4<T>(array: &mut [T]) { let l = array.len(); let n = l / 2; // l - 1 is already in the right place // l - 2 will be the last for i in 1..l - 2 { let mut f = from(i, n); while f < i { print!("."); f = from(f, n); } if f != i { println!("{} <-> {}", i, f); array.swap(i, f); } } } fn main() { let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8]; shuffle4(&mut vec); println!("{:?}", vec) }

1 <-> 4 .2 <-> 4 3 <-> 5 ..5 <-> 6 [1, 5, 2, 6, 3, 7, 4, 8]

(TODO: Add empirical time complexity charts here).

I still couldn't let go of using *cycles* directly though: particularly
because I should be able to add some heuristics to make a cycle based
approach work – counting the elements covered in the cycle makes it
possible to discover when the shuffle is finished, and I can test a
cycle to see if it visits an element lower than the current value –
at which point it can move forward.

Again, I'm not sure how to correctly estimate the time complexity of this solution.

fn from(x: usize, n: usize) -> usize { if x & 1 == 0 { x / 2 } else { n + (x - 1) / 2 } } fn shuffle5<T: Copy>(array: &mut [T]) { let l = array.len(); let n = l / 2; let mut swapped = 0; let mut pos = 0; 'outer: while swapped < l { if pos > 0 { let mut next = from(pos, n); while next != pos { if next < pos { pos += 1; continue 'outer; } next = from(next, n); } } let tmp = array[pos]; let mut cur = pos; loop { swapped += 1; let next = from(cur, n); println!("{} -> {}", next, cur); if next != pos { array[cur] = array[next]; } else { if cur != pos { array[cur] = tmp; } break; } cur = next; } println!("{}", swapped); pos += 1; } } fn main() { let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8]; shuffle5(&mut vec); println!("{:?}", vec) }

During this process, I was also constantly getting reminded of a Programming Pearl for rotating the contents of an array. The solution to that is brilliant, and not something I would have tried.

Instead of trying to keep temporary variables, it simply reverses the parts of the array around the cycle point, and then reverses the full array. This is best explained by an example: if you wanted to rotate an array by 3 elements –

-> [1, 2, 3, 4, 5, 6, 7, 8] to -> [6, 7, 8, 1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5 ... 6, 7, 8] -> [5, 4, 3, 2, 1 ... 8, 7, 6] -> [6, 7, 8, 1, 2, 3, 4, 5]

But the cycle swap mechanism will also work perfectly fine here, for the same time complexity – because there shouldn't be any short cycles that would need testing.

That, in turn, made me start thinking about this problem a little more abstractly: and I started looking around for papers for in-place permutations to see what the best State of the Art is:

Thanks to Stackoverflow, I found a paper from 1995, that also refers to Programming Pearls; Permuting in Place. Google Scholar also shows several citations that are based around finding better results for particular permutations.

^{1}

This is an oxymoron.

^{2}

This would happen to be my *third* attempt at this. I tend to
become reasonably fluent in the language, then completely stop using
it – and then start again a few months later.

Google knows the number of times I have looked up how to push, append, insert, add or insert an element into a list; and I hope they never tell me.