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)
    []
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: