Algorithms related with Randomness

Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. - From Cracking the Code Interview

public static void shuffleArray(int[] cards) {
   int temp, index;
   for (int i = 0; i < cards.length; i++){
     index = (int) (Math.random() * (cards.length - i)) + i;
     temp = cards[i];
     cards[i] = cards[index];
     cards[index] = temp;
   }
}

Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen. - From Cracking the Code Interview
public static int rand(int lower, int higher) {
 return lower + (int)(Math.random() * (higher - lower + 1));
 }
 /* pick M elements from original array. Clone original array so that
 * we don’t destroy the input. */
 public static int[] pickMRandomly(int[] original, int m) {
   int[] subset = new int[m];
   int[] array = original.clone();
   for (int j = 0; j < m; j++) {
     int index = rand(j, array.length - 1);
     subset[j] = array[index];
     array[index] = array[j]; // array[j] is now “dead”
   }
   return subset;
 }

Random number 1..5 to 1..7

int rand7()
{
 int x = 22;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;
 int r = 1 + (x % 7);
 return r;
}

int rand7() { int x = 25; while( x > 21) x = rand5() + 5*rand5() - 5;   int r = (x >> 3) + (x & 7); r = (r >= 7) ? r - 6 : r + 1; return r; } A dice, when you throw gives only 1,2,.....21 (since you are rejecting 22,23,24,25 a.k.a rejection sampling theorem) So total no. of possible are 21. No. of ways getting "1"=3 (5*1+1-5,5*2+3-5,5*3+1-1)%7+1 No. of ways getting "2"=3 (5*1+1-5,5*2+3-5,5*3+1-1)%7+1 No. of ways getting "3"=3 (5*1+2-5,5*2+4-5,5*3+2-1)%7+1 and so on.. P(1)=3/21=1/7 P(2)=3/21=1/7 and so on... Understand why these solutions are not right http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/ x=foo()+foo()-1; if (x !=8,9){ return x; } Now what's the probability here for p(1),p(2)...p(7)? no. of ways of producing "1" =1 (1+1-1) no. of ways of producing "2" =2 (2+1-1,1+2-1) and so on... Total no. of possible combination =5*5=25 P(1)=1/25; P(2)=2/25 and so on... So probabilities are not equal in this case !! return (foo() + foo()%4 -1); (foo()+foo()-1)%7+1

Also refer to http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/
Read full article from Random number 1..5 to 1..7

Random number generator in arbitrary probability distribution fashion | GeeksforGeeks

Given n numbers, each with some frequency of occurrence. Return a random number with probability proportional to its frequency of occurrence.

O(n) Space
1. Take an auxiliary array (say prefix[]) of size n.
2. Populate it with prefix sum, such that prefix[i] represents sum of numbers from 0 to i.
3. Generate a random number(say r) between 1 to Sum(including both), where Sum represents summation of input frequency array.
4. Find index of Ceil of random number generated in step #3 in the prefix array. Let the index be indexc.
5. Return the random number arr[indexc], where arr[] contains the input n numbers.

int findCeil(int arr[], int r, int l, int h)

{

    int mid;

    while (l < h)

    {

         mid = l + ((h - l) >> 1);  // Same as mid = (l+h)/2

        (r > arr[mid]) ? (l = mid + 1) : (h = mid);

    }

    return (arr[l] >= r) ? l : -1;

}

 

// The main function that returns a random number from arr[] according to

// distribution array defined by freq[]. n is size of arrays.

int myRand(int arr[], int freq[], int n)

{

    // Create and fill prefix array

    int prefix[n], i;

    prefix[0] = freq[0];

    for (i = 1; i < n; ++i)

        prefix[i] = prefix[i - 1] + freq[i];

 

    // prefix[n-1] is sum of all frequencies. Generate a random number

    // with value from 1 to this sum

    int r = (rand() % prefix[n - 1]) + 1;

 

    // Find index of ceiling of r in prefix arrat

    int indexc = findCeil(prefix, r, 0, n - 1);

    return arr[indexc];

}

One simple method is to take an auxiliary array (say aux[]) and duplicate the numbers according to their frequency of occurrence. Generate a random number(say r) between 0 to Sum-1(including both), where Sum represents summation of frequency array (freq[] in above example). Return the random number aux[r] (Implementation of this method is left as an exercise to the readers).

The limitation of the above method discussed above is huge memory consumption when frequency of occurrence is high. 

Read full article from Random number generator in arbitrary probability distribution fashion | GeeksforGeeks