lets say you wants to generate random number between i to j e.g.
[ i,j ) excluding upper limit. One standard pattern for accomplishing this is:
Min + (int)(Math.random() * ((Max - Min) + 1))
The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1.
In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered.
Math.random() * ( Max - Min )
This returns a value in the range [0,Max-Min).
For example if you want [5,10] you need cover 5 integer values so you use
Math.random() * 5 This would return a value in the range [0,5)
Now you need to shift this range up to the range that you are targeting. You do this by adding the Min value.
Min + (Math.random() * (Max - Min))
You now will get a value in the range [Min,Max). Following our example, that means [5,10):
5 + (Math.random() * (10 - 5))
But, this is still doesn't include Max and you are getting a double value.
In order to get the Max value included, you need to add 1 to your range parameter (Max - Min) and then truncate the decimal part by casting to an int. This is accomplished via:
Min + (int)(Math.random() * ((Max - Min) + 1))
And there you have it. A random integer value in the range [Min,Max],
or per the example [5,10]:
5 + (int)(Math.random() * ((10 - 5) + 1))
Algorithm:
This is a very well known algorithm known as Knuth-Shuffle. If you aren’t one
of the lucky few to have already know this algorithm, read on.Let’s start
with a brute force approach: we could randomly selecting items and put them
into a new array. We must make sure that we don’t pick the same item twice
though by somehow marking the node as dead.
Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Mark element as dead: [1] [2] [3] [X] [5]
The tricky part is, how do we mark [4] as dead such that we prevent that
element from being picked again? One way to do it is to swap the now-dead [4]
with the first element in the array:
Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Swap dead element: [X] [2] [3] [1] [5]
Array: [X] [2] [3] [1] [5]
Randomly select 3: [4] [3] [?] [?] [?]
Swap dead element: [X] [X] [2] [1] [5]
By doing it this way, it’s much easier for the algorithm to "know" that the
first k elements are dead than that the third, fourth, nineth, etc elements
are dead. We can also optimize this by merging the shuffled array and the
original array.
Randomly select 4: [4] [2] [3] [1] [5]
Randomly select 3: [4] [3] [2] [1] [5]
Working Solution: Its Totally Worthy & Pure Shuffle Used in Our Music Player
class random
{
public static void shuffleArray(int[] cards)
{
int temp, index;int ar[]=new int[cards.length];
int count=0;
for (int i = 0; i < cards.length; i++)
{
index = (int) (Math.random() * (cards.length - i)) + i;
//generate random index between i to n here we don't need to add 1 in last
//to range as array indexes start at 0 if we add 1 to cards.length-i then
//we might get index > n-1 which throws array out of index bound exception
ar[count++]=index;
temp = cards[i];
cards[i] = cards[index];
cards[index] = temp;
}
for(int i=0;i<ar.length;i++)
System.out.print(ar[i] + " ");
}
public static void main(String a[])
{ int ar[]=new int[]{1,2,3,4,5};
shuffleArray(ar);
System.out.println();
for(int i=0;i<ar.length;i++)
System.out.print(ar[i] + " " );
}
}
Time Complexity: O(N)
Space Complexity: O(1)
Run Here https://ideone.com/UTk9V
https://ideone.com/B0YEn - Read from Consol
