Mathematics7

Q7. Randomly generate a weighted index for a given array. The probability for bigger number should be more than smaller number.

For example: if given array is {15, 18, 17, 15, 35} then generate a random index (from 0 to 4), but since 35 is the biggest number so probability of getting index 4 should be maximum. Probability should also be proportional to the number like if probability to generate index for number 50 is p then probability to generate index for number 25 should be p/2.

Answer:

• First take a small problem suppose array is {1,2,3}
• Now if probability for getting 1 is p, then probability for getting 2 is 2p and probability for getting 3 is 3p.
• Sum all numbers of the array. 1+2+3 = 6. 
• Generate a random number from 1 to 6. 
• Return 1 if generated number is 1. Here probability for getting 1 is 1/6.
• Return 2 if generated number is 2 or 3. Here probability for getting 2 is 2/6.
• Return 3 if generated number is 4 or 5 or 6. Here probability for getting 3 is 3/6.

import java.util.Random;

public class Mathematics7 {
    public int getRandomIndex(int[] array) {
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }

        int randomNumber = new Random().nextInt(sum);
        int currentSum = 0;
        int index;
        for (index = 0; index < array.length; index++) {
            currentSum += array[index];
            if (randomNumber < currentSum)
                break;
        }
        return index;
    }

    public static void main(String args[]) {
        Mathematics7 w = new Mathematics7();
        int array[] = { 15, 18, 17, 14, 35 };
        int count[] = new int[array.length];

        // generate random index 100 times for the array
        // the biggest number should get maximum chances
        for (int i = 0; i < 100; i++) {
            int randomIndex = w.getRandomIndex(array);
            count[randomIndex]++;
        }

        for (int i = 0; i < count.length; i++)
            System.out.println("array[" + i + "]= " + array[i] + "->" + count[i]);
    }
}