CODEWITHSUNDEEP
randomshuffle
code animal
code animal

Reputation: 21

shuffle algorithm with only random 0, 1

I just read some interview question on the internet and made me curious at the solution.

Problem is like this.

Given a list of numbers and a rand(0,1) function, which returns a random integer between 0 and 1. Provide an algorithm to randomly sort the given list, based on the output of the rand() function, which should be called once for every number on the list.

It seems asking to generate a random number with only 0 and 1 for shuffle. And I came up with this solution.

int random(int array_index, int array size)
{
    return (array_index * 41 * (array_size + rand(0,1)) % array_size;
}

But I feel this is not good enough since it depends on array_index.

Anyone has better answer for this?

Upvotes: 2

Views: 1383

Answers (4)

Xantix
Xantix

Reputation: 3331

Suppose I have a 10 element list. Then there are 10! = 3628800 different ways of ordering it.

If I can call rand(0,1) only 10 times, I can generate only 2^10 = 1024 different binary sequences.

There is no way to uniquely identify one of the 10! orderings with a number between 0 and 1024. That is we cannot perform an unbiased shuffle. (except for lists of greater than 3 elements). So, we can now focus on choosing an easy to implement biased shuffling.

For example:

result = new List<int>();

foreach( int i in list )
{
  int r = rand(0,1);

  if( r == 0 )
    result.Prepend(i);
  else
    result.Append(i);
}
return result;

This is very biased to putting elements further in the list away from the middle of the list.

Upvotes: 0

Sajal Jain
Sajal Jain

Reputation: 708

Let the array size be N

To shuffle the list of numbers randomly we use the following strategy.

For the first element we find a position out of the all available N choices.
Then, the second element has N-1 choices and so on. 
We generate the N! possible outcomes which ensures all are equi-probable.

Now to generate the position randomly out of (say N) choices we do the following; (We do the same for N-1, N-2 ...)

Use Divide - And - Conquer.
First modify N to (Least Power of 2 >= N) Example: For N=5, modified_N=8 
Run rand(0,1) - 
If 0 - we the position is from 1 to modified_N/2
Else - the position is in modified_N/2+1 to modified_N

We do this recursively till we find the final position. 
If the final position is between N+1 and modified_N we run this procedure again.

This way we can find 1 position at a time randomly using rand(0,1)

Upvotes: 0

Mizuho
Mizuho

Reputation: 90

I'll just write mine in Ruby, since I use it more.

def random_sort(numbers)
  sorted = Array.new
  index = 0
  numbers.each do |number|
    while rand(1)
      index += 1
    end

    index = index % numbers.length
    while numbers[index] != nil
      if index > numbers.length - 1
        index = 0
        continue
      end
      index += 1
    end

    sorted[index] = number
  end

  return sorted
end

Upvotes: 0

Gareth Bowen
Gareth Bowen

Reputation: 949

You should use the Fisher-Yates Shuffle algorithm, which performs a truly random shuffle in O(n) time (ie: "called once for every number on the list").

To shuffle an array a of n elements (indices 0..n-1):
    for i from n − 1 downto 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

Upvotes: 2

Related Questions