Shuffle An Array

June 30, 2020

Today’s exercise comes to us from Leetcode via Reddit:

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

The Reddit poster claims to be new to Scheme and functional programming, and was thinking of a solution using length and list-ref, but couldn’t solve the problem.

Your task is to show the student how to solve the problem. When you are
finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: