#+TITLE: In Place Permutations

A cautionary tale wherein I successfully nerd-snipe[fn:oxy] myself.

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

#+begin_quote
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].
#+end_quote

...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: 
#+begin_src scheme :results output :exports both
(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)))
#+end_src

#+RESULTS:
: (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.

#+begin_src scheme :results output :exports both
(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)))
#+end_src

#+RESULTS:
: (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[fn:rust]. 

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.

#+begin_src rust :results output :exports both
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)
}
#+end_src

#+RESULTS:
: [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.

#+begin_src rust :resuts output :exports both
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)
}
#+end_src

#+RESULTS:
: 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.

#+begin_src rust
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)
}
#+end_src

#+RESULTS:
#+begin_example
0 -> 0
1
4 -> 1
2 -> 4
1 -> 2
4
5 -> 3
6 -> 5
3 -> 6
7
7 -> 7
8
[1, 5, 2, 6, 3, 7, 4, 8]
#+end_example

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

#+begin_src
-> [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]
#+end_src

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.




[fn:oxy] This is an oxymoron.

[fn:rust] 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.