Shuffle An Array
June 30, 2020
Assuming the input is a properly-formed list with an even number of elements, the following program solves the problem:
(define (leetcode1470 input-list) (let loop1 ((turtles input-list) (hares input-list) (tnorf (list))) (if (pair? hares) (loop1 (cdr turtles) (cddr hares) (cons (car turtles) tnorf)) (let loop2 ((tnorf tnorf) (kcab (reverse turtles)) (result (list))) (if (pair? tnorf) (loop2 (cdr tnorf) (cdr kcab) (cons (car tnorf) (cons (car kcab) result))) result)))))
For example:
> (leetcode1470 '(1 2 3 4 a b c d)) (1 a 2 b 3 c 4 d)
The first loop splits the list using Robert Floyd’s turtle-and-hare algorithm. The turtle and hare both advance through the list, starting at the beginning, but the hare runs twice as fast as the turtle, so when the hare reaches the end of the list, the turtle is at the mid-point. At the same time, the items in the front half of the list are accumulated, in reverse, in tnorf.
The second loop assembles the result. The two halves of the list, in reverse order, are in tnorf and kcab, and the loop just runs through them, writing each item to the output. It is easier to work from back to front because that is the natural order for cons.
Loop1 and loop2 are each executed n times, for an O(n) algorithm.
You can run the program at https://ideone.com/jgMZ4G.
Sample output:
Another version using generators
A quick naive implementation in Haskell:
Here’s a solution in Python.
Output:
A python implementation
A pythhon implementation
A C implementation
Clojure:
Test:
Though checks can be added to ensure that input is a sequence that has even amount of elements:
Test: