CareerCup

void shuffle(Element* array, int size）{
    for (int i=0; i<size; i++） {
      ind = rand(i,size);
      swap(array[i], array[ind]);
    }
}

// k is a random number between 0, i. Prob = 1/(i+1)
// Total Prob = 1/(1 * 2 * ... * N) = 1/(N!)
// this makes the shuffle to be uniformly randomly selected from the possible N! permutations of the array.
void knuth_shuffle( int * array, int size )
{
for ( int i = size - 1; i >= 0; i++ )
{
int k = (int)(rand() * i);
swap( &array[i], &array[k] );
}
}

void shuffle(Element* array, int size）{
    for (int i=0; i<size; i++） {
        int toSwap = Rand()%size;
        if(toSwap!=i) {
            Element temp = array[toSwap];
            array[toSwap] = array[i];
            array[i] = temp;
        }
    }
}

Why don't people try proving their algorithms?

btw, lookup fischer yates shuffle.

How about rotating left by one position with a probability of 1/n?

How about making the new index as:
1) Generate a random no. 'r' initially once
2) Make new_index = (old_index + r)%n

I think it does. Iterate through all the cards, for every card, swap it with a random card that has not been visited yet. So, random will run from i + 1 to card count - 1 where i is the current position.

Generate a random number k between 1 and n and rotate the array to the left (or right) k times.
This way each element has a 1/n probability of remaining there

Manish - your solution just wont work. When, k=1,2,3, none of the elements will be in its original position. When k=4, all elements will be in their original position, which is the only case when it works. So, the probability isn't 1/n.

there are n! of permutations. Let us numbering them from 1 to n! and select 1 random number between 1 and n! (inclusive), and call this k, so kth permutation of this current array will be the result after shuffle.

@emotionalBlind
I guess you are referring to the Knuth shuffle, which I believe is correct.

int* shuffle_array(const int* nArray, const int nSize)
{
int* p = new int(nSize);
//float a = rand();
for (int i = 0; i < nSize; i ++) {
float a = rand();
int n = a*(i+1);
swap(p[i], p[n]);
}
return p;
}

Dudes...
The knuth shuffle is not order n. It's n^2.

how about :
1. loop through each number in the given array
2. for each element at index i, generate a random number between 1 and n. if the number is same as i (the probability of this happening is 1/n), the number needs to swapped out. hence save this index using a temp variable (say last_element_to_be_swapped).
3. now continue with the next element and perform step 2. if it needs to swapped out, swap it with last_element_to_be_swapped. save the current index to last_element_to_be_swapped so that we can swap for further iterations.

As long as we find two elements that needs to be swapped, we are good. The only exception is when we only find one element that needs to be swapped, then we will not be able to shuffle with any other element. I am thinking of rerunning the loop again to handle this case. there are really low chances we run into same case again.

btb, this approach take O(n) obviously.

Here is my answer, how about it?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

void shuffle(int a[], const int n);

int main()
{
	int a[5]={1,2,3,4,5};
	const int n = 5;
	shuffle(a,n);
        return 0;
}

void shuffle(int a[], const int n)
{
	time_t t;
	srand((unsigned) time (&t)); //srand guarantees that each rand() function will
                                     //generate a really random number
	int *b=new int[n];
	int i,j;
	for(i=0;i<n;i++)
		b[i]=0;
	for(i=0;i<n;i++)
	{
		j=rand()%n;
		while(b[j] != 0)    //if there b[j] has already saved a value
			j = (j+1)%n;
		b[j]=a[i];
	}
	for(i=0;i<n;i++)
		a[i]=b[i];
	delete []b;
}