Pls I need help on how to make my function in javascript NOT to create a random number twice in one output.

Question

My function may generate: 50, 66, 60, 67,100, 51, 50, 67, 88, 74. You can see that 50 and 67 were generated twice. That is actually what I don't want. But I still want a total number of 10 numbers to be generated in one output whenever the function gen() is called once. Thanks you so much as you help me out.
https://code.sololearn.com/WQID6U6p1Mv8/?ref=app

Answer 1

CamelBeatsSnake The reason I claimed mine solution to be more efficient was that it didn't need to check all the numbers already picked to make sure that the newly-selected number had already been chosen. Checking through the generatedNums array takes linear time (O(len) where len is the length of generatedNums), and this needs to be done n times. This works out at a running time of O(n^2) (if I understand that correctly).

My method creates an array at a running time of O(high-low), then choosing the numbers in linear time O(n) giving a total running time of O(n+high-low) (again, I think), but it obviously uses more memory than your solution.

I wouldn't expect my solution to run faster than yours with these numbers (n = 10, etc.) but as n increases to a much larger number, I would expect mine to run much quicker. This is, of course, ignoring the fact that your program theoretically could take an infinite running time if if keeps selecting numbers that have already been chosen.

Answer 2

This should work:

function gen(n) {
const generatedNums = [];

while (generatedNums.length < n) {
let num = Math.round(Math.random() * 100);
if (num<50) {
num+=50;
}
if (generatedNums.includes(num)) {
continue;
} else {
generatedNums.push(num);
console.log(num);
}
}
}

gen(10);

Answer 3

This was my solution for this problem. More efficient (at least time-wise) than checking if each number had already been selected. The idea was to create an array of all possible numbers, pick one at random, switch it to the end of the list, then reduce the effective length of the array by 1 to stop it being picked again.

https://code.sololearn.com/WH5keATN2B09/?ref=app

Answer 4

Russ Nice approach.

I wasn't thinking about performance since it didn't seem relevant for a small set of data/small application the OP had. That said, I am curious about your statement that your solution is more efficient.

I ran your solution against mine several times at both jsben.ch and jsbench.me and it came out slower every time.

I know they're not exactly comparable because yours allows a range to be passed in which is really nice. I thought about allowing that too but decided against it because, again, I didn't the OP had an immediate use for it because he hadn't asked for it.

Answer 5

Russ Thanks for the details. Yeah, I was thinking about the memory usage as well but I see what you mean now. Thanks again 👍

Answer 6

David Carroll I have had a quick look at your code and I feel that it doesn't correctly do the job if start is not 0 (as is the case in this question). If I set max to 100 and start to 50 in your code, I see a disproportionate number of 50s appearing in the sample (because when a number less than 50 is chosen, it gets changed to the minimum number).

You do raise a good challenge though, that is to accomplish the same task without populating an array if all possible values, which I will attempt to solve when I get chance, though I'm sure you will get there first!

Edit: On further analysis, your code seems to return many more 1s and 2s than 8s and 9s and will only return a 10 if there is a 9 with it 🤔

Also, after further thought, I don't think the algorithm on which my solution was based can be bettered all that easily.

Answer 7

Russ Indeed... my attempt was a quick proof of concept emphasizing:

the calculation of values to
minimize the memory
footprint

... while preserving the more deterministic and lower cyclomatic complexity accomplished in your code. 😉

The algorithm in my code can certainly be extended to satisfy additional requirements for a more randomized distribution of values across a low / high range. 👌

You seem to have picked up on some additional requirements inferred from the OP's code. I just focused on the explicitly stated requirement in the question which is to generate a specified quantity of a unique set of (cough cough) "random" values.

While Math.random() is less random than the function name implies, it seemed to satisfy the OP's degree of randomness based on his follow up responses. 👌

Since my time is so spread thin these days as an Application Architect for several large platform initiatives, I doubt I'll be tinkering beyond what I've already done. 😉

Answer 8

Thanks a lot, it works. Let me study your code now and see the logic behind it.

Answer 9

Apongpoh Gilbert Your code doesn't solve the problem. There's a chance that the same number can be outputted more than once.

Answer 10

Martin Taylor I wasn't thinking of that exactly, but I feel I have looked at it before, so it must have been in the back of my mind somewhere.

Answer 11

A faster way would be using a Set data structure to check if the number has already been chosen. A Set can check if it contains an element in amortized O(1) time only.

EDIT:
Theres an even faster algorithm by Floyd which is also easy to implement:
https://stackoverflow.com/a/2394292

Heres my attempt (i recommend to use Floyd's instead)
https://code.sololearn.com/WCARU2RfzUda/?ref=app

Extra: heres an interesting article about random sampling
https://eyalsch.wordpress.com/2010/04/01/random-sample/

Answer 12

David Carroll Sure, that's perfectly understandable.

Having had another look at your solution, I feel that your Math.floor function would be better off being Math.ceil. I think this would address the issue I raised on my edit on my previous comment.

I do have a couple of questions though. Your algorithm appears to choose the next unchosen number if it picks an already chosen one. Does that an equally random sample? My thought is that after the first number is picked (say 5), I think the next number has twice the chance of being picked than the others (both 5 and 6 mean 6 is the next one picked). I wonder whether that means samples with consecutive numbers become disproportionately more likely?

Also, I wondered about the time complexity of your code. If it searches through all the previously-chosen numbers each time, isn't that O(n^2)?

Answer 13

Russ and David Carroll you may be interested in Floyd's Algorithm, i have written it in recursive form along with an informal proof of correctness here:

https://code.sololearn.com/WsBVwi3dHIww/?ref=app

Answer 14

Simply use <=

Answer 15

Russ. Thanks a lot, but I don't quite understand your solution. Please don't worry, I will get to understand it by the time I get deeper in learning Javascript. I so much appreciate your contributions

Answer 16

Nice variety of solutions here.

My approach is a proof of concept (POC) that builds on the reduced cyclomatic complexity presented in the code by Russ.

Rather than filling an array with all possible values, I'm calculating the values that would have been located in the randomly generated index positions of a populated array.

I probably could have tightened up the code a bit... but I believe it satisfies my immediate goals for this POC of minimal memory usage, minimal cycles, and optimal performance with a deterministic number of calls to Math.random().

https://code.sololearn.com/c67a222A132A/?ref=app

Answer 17

Yo hablo español. No Inglés