# Array Shuffling

Write a program that takes a sorted integer array, shuffles all the elements in such a way that for every i there must exist a j such that, one of the following is satisfied:

a[i] < a[j] < a[i+1]
a[i] > a[j] > a[i+1]


i and j are within the bounds of array.

If there are not many distinct elements, you must show an error.

For example,

Input: 1, 2
Output: Error

Input: 1, 2, 3, 4, 5, 6, 7
Output: 7, 1, 4, 2, 5, 3, 6

Input: 1, 2, 2, 4, 5, 6, 7
Output: 1, 4, 6, 2, 5, 2, 7

Input: 1, 2, 2, 3
Output: Error

Input: 1, 5, 7, 7, 11
Output: Error


There may be more than one possible correctly shuffled arrays. You just have to solve for 1 correct solution.

Input array can have repeated elements, this requirement makes the solution tricky, otherwise a sort and skip would have worked.

Being able to have duplicates in input also makes it different from The Strange Unsorting Machine for Nefarious Purposes . And a correct solution is much trickier than the that.

The output must be of same size as input array and all elements from the input array must exist at some position in the output array.

How to take input: The program must take input either through console input or a simple delimited text file.

How to output: The program must output to the console.

What to output: Program must output both the input and the output array in following format

Input: 1, 2, 3, 4, 5, 6, 7
Output: 7, 1, 4, 2, 5, 3, 6


If input cannot be shuffled as required, the output should look like

Input: 1, 2, 3
Output: Error


Shortest code (byte count) wins.

BONUS 1: Deduct 10 points from your count if your solution can work on unsorted inputs.

BONUS 2: Deduct 20 points from your count if your solution can find more than 1 (not all) solutions for the same input. To qualify for this bonus, your additional solution must not be just a reversed output of the other solution.

• This is essentially the same as The Strange Unsorting Machine for Nefarious Purposes Feb 20, 2014 at 19:24
• It is different because it allows duplicate items in the input. Feb 20, 2014 at 19:28
• I've a solution that works for arrays up to seven elements. Seems up to the specifications so far Feb 20, 2014 at 20:23
• I've code that finds all solutions, the brute force way. Haskell: u c=filter(\d->and$map((a,b)->any(\x->(a<x&&x<b)||(a>x&&x>b))d)$zip d (tail d))$permutations c ... just need to do the I/O. Of course being haskell I/O is no fun Feb 20, 2014 at 20:24 • This question is very similar also: codegolf.stackexchange.com/questions/18306/alternating-sort. – user10766 Feb 20, 2014 at 21:27 ## 1 Answer # Haskell, 311276 (-30 bonus=246) import Data.List m=map w=putStrLn b=(intercalate",").(m show) o="Output: " z[]=[o++"Error"] z a=m((o++).b)a main=do r<-getLine let q=m read(words r)::[Int] w$"Input: "++b q
mapM_ w$z$filter(\d->and$m(\(a,b)->any(\x->(a<x&&x<b)||(a>x&&x>b))d)$zip d(tail d))\$permutations q


Compile with ghc, Run from the command line, input is a single line with space delimited numbers, eg echo 1 2 3 4|shuffle. This is a brute force solution so is quite likely to be slow for large input lists. It prints all the solutions.