expLog

In Place Permutations

A cautionary tale wherein I successfully nerd-snipe1 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 again2.

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.

view source