How do I generate a random no. between a range (lowerindex to higherindex) that is not equal any no. that has been randomly generated before …
also, the time complexity should be less , i.e i don’t want to generate continuously a random no. until I find a no. that has not been generated before .
Thanks in advance!
Assuming you want uniform distribution, the best time complexity you’ll get is O(n), where n is the number of previous generated numbers. I’m not aware of any way to break this theoretical limit.
Tell us more about your use case, and we might be able to give a better answer.
1 Like
Since you will have a fixed set of numbers to pick from (lowerindex to higherindex), you could first create an array with all of the numbers in the set. This will take O(n) time and require O(n) space. Next you could use the Richard Durstenfeld’s rework of the Fisher-Yates Shuffle algorithm which will randomize the order of the numbers in the array. The Fisher-Yates Shuffle algorithm performs the randomization in place, so no extra memory needed and take O(n) time. So the overall time complexity would still be O(n) using the steps I have described.
Was there a particular reason you do not want to continuously generate random number until a number has not been generated before? As @lionel-rowe mentioned, if you could provide us more information in how you plan to use these random numbers, we may be able give you a better answer.
1 Like
Got it! thanks! @lionel-rowe @camperextraordinaire … the Fisher-Yates Shuffle did the work for me!
function randomizeIt(arr)
{ var l=arr.length, randomIndex, temp ; //randomIndex is for random index of arr
while(l)
{ randomIndex = Math.floor(Math.random()*l--) // creates a random no. b/w 0 to l-1
/*swappinig the element at random index with the last element
so that it gets out of randomize loop */
temp=arr[l];
arr[l] = arr[randomIndex] ;
arr[randomIndex] = temp;
}
return arr; }
This returned an array with all elements shuffled in it with time complexity of O(n) ! Thanks !