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

Pages: 1 2

### 8 Responses to “Shuffle An Array”

1. Milbrae said
```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:

```[5, 1, 19, 12, 15, 14, 18, 18, 16, 4]
[5, 14, 1, 18, 19, 18, 12, 16, 15, 4]```
2. Milbrae said

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))))
```
3. Larry Lee said

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)
```
4. Daniel said

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:

```['1', 'a', '2', 'b', '3', 'c', '4', 'd']
```
5. Xero said

A python implementation

```def shuffle(xs):
n = len(xs)//2
return list(reduce(λ a,b: a+b, zip(xs[:n], xs[n:])))
```
6. Xero said

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:])))
```
7. Xero said

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);
}
```
8. Clojure:

```(defn shuffle-array [arr]
(let [half (/ (count arr) 2)]
(into [] (interleave (take half arr) (drop half arr)))))
```

Test:

```(shuffle-array [:a :b :c 1 2 3])
[:a 1 :b 2 :c 3]
(shuffle-array [:a :b :c 1 2 3 4])
[:a 2 :b 3 :c 4]
```

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:

```(shuffle-array [:a :b :c 1 2 3])
[:a 1 :b 2 :c 3]
(shuffle-array [:a :b :c 1 2 3 4])
[]
(shuffle-array 1)
[]
```