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.
import random import itertools def shuffle(arr): """ """ l = len(arr) if l < 2 or l % 2 != 0: return [] l2 = l // 2 return list(itertools.chain(*[[arr[x], arr[x+l2]] for x in range(l2)])) n = 10 a = [random.randint(0, n * 2) for k in range(n)] print ("%s\n%s" % (a, shuffle(a)))Sample output:
Another version using generators
import random def shuffle2(arr): """ """ l = len(arr) if l < 2 or l % 2 != 0: return [] l2 = l // 2 for x in range(l2): yield arr[x] yield arr[x+l2] n = 10 a = [random.randint(0, n * 2) for k in range(n)] print ("%s\n%s" % (a, list(shuffle2(a))))A quick naive implementation in Haskell:
shuffle :: [Integer] -> [Integer] shuffle xs | length xs `mod` 2 == 0 = let n = div (length xs) 2 in foldr (\(x, y) acc -> x:y:acc) [] $ zip (take n xs) (drop n xs)Here’s a solution in Python.
def shuffle(l): return [x for pair in zip(l, l[len(l) // 2:]) for x in pair] print(shuffle(['1', '2', '3', '4', 'a', 'b', 'c', 'd']))Output:
A python implementation
def shuffle(xs): n = len(xs)//2 return list(reduce(λ a,b: a+b, zip(xs[:n], xs[n:])))A pythhon implementation
from functools import reduce def shuffle(xs): n = len(xs)//2 return list(reduce(lambda a,b: a+b, zip(xs[:n], xs[n:])))A C implementation
#include <stdlib.h> void *shuffle (int *arr, int len) { int n = len/2; int *first_half = (int *) calloc(n, sizeof(int)); int *second_half = (int *) calloc(n, sizeof(int)); int i, j; for (i=0; i < n; ++i) { first_half[i] = arr[i]; second_half[i] = arr[i+n]; } for (i=0; i<n; ++i) { j = 2*i; arr[j] = first_half[i]; arr[j+1] = second_half[i]; } free (first_half); free (second_half); }Clojure:
(defn shuffle-array [arr] (let [half (/ (count arr) 2)] (into [] (interleave (take half arr) (drop half arr)))))Test:
Though checks can be added to ensure that input is a sequence that has even amount of elements:
(defn shuffle-array [arr] (if (and (sequential? arr) (= 0 (mod (count arr) 2))) (let [half (/ (count arr) 2)] (into [] (interleave (take half arr) (drop half arr)))) []))Test: