CareerCup

Given an integer array 'a' of the length 'N' the problem can be solved as follows:
For each 'i' in 0 to N-1:
(i) generate a random number 'k' that is betweem 'i' and N-1
(ii) swap elements a[i] and a[k]

public static void shuffle(int[] a) {
	int N = a.length;

	for (int i = 0; i < N; i++) {
		int k = i + random()*(N-i)  	// random in (i, N-1)
		int aux = a[i];
		a[i] = a[k];
		a[k] = aux;
	}
}

This algorithm yields in a uniform shuffling, hence all possible permutations are equally possible.

public static void shuffle(int[] a) {
		
		int n = a.length;

		for (int i = 0; i < a.length - 1; i++) {

			int randNum = (int) (Math.random() * (n - i));
			swap(randNum, n - i - 1, a);
		}

	}

	public static void swap(int e1, int e2, int[] arr) {

		int temp = arr[e1];
		arr[e1] = arr[e2];
		arr[e2] = temp; 
	}

public int[] shuffle(int[] array) {

       int randomIndex;
       int temp;
       for (int i = 0; i < array.length; i++) {
           randomIndex = (int) Math.floor(random()*array.length);
           temp = array[i];
           array[i] = array[randomIndex];
           array[randomIndex] = temp;
       }
       return array;
   }

# Cmdline Input:
# prog val1 val2 ... valN

nums = ARGV.map { |v| v.to_i }
n = nums.size

res = []
idxs = (0...n).to_a
nums.each do |num|
  i = (rand * idxs.size).floor
  res[idxs[i]] = num
  idxs.delete_at i
end

puts "Shuffled array: #{res}"

function newRandomArray() {

var arr = [1,5,3,9,0,11];
var newArr = [];

for (var i = arr.length - 1; i >= 0; i--){
var random = Math.floor(Math.random()*arr.length);
newArr.push(arr[random]);
arr.splice(random, 1);
}

document.getElementById("out").innerHTML = newArr;
}

function newRandomArray() {
	
    var arr = [1,5,3,9,0,11];
    var newArr = [];
    
    for (var i = arr.length - 1; i >= 0; i--){
    	var random  = Math.floor(Math.random()*arr.length);
        newArr.push(arr[random]);
        arr.splice(random, 1);
    }
    
    document.getElementById("out").innerHTML = newArr;
}

public class RandomizeArrayProblem {

    public static int binRandom(){
        return Math.random() < 0.5 ? 0 : 1;
    }

    public static int nRandom(int n){
        int result = 0;
        while(--n >= 0)
            result += binRandom();
        return result;
    }

    public static void exch(int [] a, int i, int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void shuffle(int [] a){
        for(int i = 0; i < a.length; i++)
            exch(a, i, nRandom(i));
    }

    public static void main(String[] args) {
        int [] testArray =  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        shuffle(testArray);
        System.out.println(Arrays.toString(testArray));
    }

}

public static String randomArray(int[] array){
Random random = new Random();
int index ;
int swap;
for(int i = 0;i < array.length;i ++){
index = random.nextInt(array.length);
swap = array[i];
array[i] = array[index];
array[index] = swap;
}
return Arrays.toString(array);
}

public static String randomArray(int[] array){
Random random = new Random();
int index ;
int swap;
for(int i = 0;i < array.length;i ++){
index = random.nextInt(array.length);
swap = array[i];
array[i] = array[index];
array[index] = swap;
}
return Arrays.toString(array);
}

from random import randint
n = 10
arr =[]
def gen_random(n, arr):
	num = randint(0, n-1)
	if not num in arr and num != i:
		arr.append(num)
	else:
		gen_random(n, arr)
	return num

for i in range(n):
	num = gen_random(n, arr)
	
print(arr)

from random import randint
n = 10
arr =[]
def gen_random(n, arr):
num = randint(0, n-1)
if not num in arr and num != i:
arr.append(num)
else:
gen_random(n, arr)
return num

for i in range(n):
num = gen_random(n, arr)

print(arr)

from random import randint
n = 10
arr =[]
def gen_random(n, arr):
	num = randint(0, n-1)
	if not num in arr and num != i:
		arr.append(num)
	else:
		gen_random(n, arr)
	return num

for i in range(n):
	num = gen_random(n, arr)
	
print(arr)

int *shuffle(int* source, int N)
{
	for (int i = N-1; i > 0; i--)
	{
		int p = random()*i;
		int tmp = source[i];
		source[i] = source[p];
		source[p] = tmp;
	}
	return source;

}

PHP has a really easy way to solve the problem with

usort($array, 'random');

However, I'll show a custom solution to do the same thing. Note that this code only works for indexed arrays, though upon request I can extend it to work for associative arrays.

function arrShuffle($array)
{
	
	// Prevent errors.
	if (count($array) === 1) {
		return $array;
	}
	
	$newArr = array();
	foreach ($array as $key => $value) {
		
		if ($key === 0) {
			
			$newArr[] = $value;
			continue;
			
		}
		
		if (random() === 1) {

			// Add the current value to the stack.
			$newArr[$key] = $value; 
			
		} else {
			
			// Switch the value with the last value.
			$newArr[$key] = $newArr[$key-1];
			$newArr[$key-1] = $value;
			
		}
		
	}
	
	return $newArr;
}

static int[] shuffle(int[] A) {
	Random rand = new Random();
	int[] shuffledArray = new int[A.Length];
	Array.Copy(A, shuffledArray, A.Length);
	for (int i = 0; i < shuffledArray.Length; i++) {
		swap(ref shuffledArray[i], 
		ref shuffledArray[Convert.ToInt32(rand.NextDouble() * (shuffledArray.Length - 1))]);
	}
	return shuffledArray;
}

Suppose that we have a function that return a random number belong to internal [0,1), then we can draw a fuction as fllow:

void shuffle(int A[], int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int offset = random() * (n - i);
		swap(A[i], A[i] + offset);
	}
}

ssss

import java.util.Arrays;
import java.util.Random;

public class RandomizeArray {
    private Random rand = new Random();

    public void randomizeArray(int[] a) {
        for(int i = 0; i < a.length; i++) {
            int index = rand.nextInt(a.length);
            swapValues(a,i, rand.nextInt(a.length));
        }
    }

    private void swapValues(int[] a, int i, int i1) {
        int temp = a[i];
        a[i] = a[i1];
        a[i1] = temp;
    }

    public static void main(String[] args) {
        RandomizeArray randomizeArray = new RandomizeArray();
        int a[] = {1,2,3,4,5};
        for (int i = 0; i < a.length; i++) {
            randomizeArray.randomizeArray(a);
            System.out.println(Arrays.toString(a));
        }

    }
}

import java.util.Arrays;
import java.util.Random;

public class RandomizeArray {
    private Random rand = new Random();

    public void randomizeArray(int[] a) {
        for(int i = 0; i < a.length; i++) {
            int index = rand.nextInt(a.length);
            swapValues(a,i, rand.nextInt(a.length));
        }
    }

    private void swapValues(int[] a, int i, int i1) {
        int temp = a[i];
        a[i] = a[i1];
        a[i1] = temp;
    }

    public static void main(String[] args) {
        RandomizeArray randomizeArray = new RandomizeArray();
        int a[] = {1,2,3,4,5};
        for (int i = 0; i < a.length; i++) {
            randomizeArray.randomizeArray(a);
            System.out.println(Arrays.toString(a));
        }

    }
}

I was asked that in a Starbuck interview. I came up with the normal solution of recreating the array and swaping away the values.

But the interviewer interesting enough he brough a surprising fact. He mentioned that: using the random function in a very close time frame will have clustered values as it depends this function depends on time to calculate the random value.

So for this solution I'll introduce an small delay of a 10th of a millisecond to enable the random function to be more fairly distribute.

Also I'm reusing the array as it did mention that it returns an array but not a new array.

using System.Threading;
static public T[] GetRandomizedArray(T[] A)
{
	Random r = new Random();
	
	for(int i = 0; i > A.Length; i++)
	{
		// The value is between 0..1 not inclusive so it will never
		// A.Length when multiply
		double rValue = r.NextDouble();
		int newIndex = rValue*(A.Length);
		
		T swap = A[newIndex];
		A[newIndex] = A[i];
		A[i] = swap;

		// Max of 10th of a Millisecond wait to get fairly distributed random values
		long waitTicks = (long) rValue*TimeSpan.TicksPerMillisecond / 10;

		Thread.CurrentThred.Sleep(TimeSpan.FromTicks(waitTicks));
	}
}