Random Numbers

[kris.c]

hi all,
I am required to generate an array having 100 random numbers, where there is absolutely no repetition and the case where the ith element of the array is the number " i " itself is not allowed ..
I found some ideas where we could generate pseudo random numbers using the idea:
x(n+1) = (x(n)*P1 + P2) (mod N) .
where x(n) is the nth element,
P1 and P2 are constants
N is also a constant.. the value of x0 must be chosen appropriately..
This does not guarantee absolute randomness..
Can some one help me with this please...

[iamthwee]

couldn't you just fill an array with numbers from 1-100.

Then shuffle them inside the array?

[Exodust]

Here's what you can do : First, generate 100 random numbers, using rand() function (I think you first have to seed the function with some variable value.)

Now, check for any repeated numbers, or numbers that are on the index same as themselves using recursion; change the number again using another rand() call. keep track of the number of changes made.

Now, repeat the above process using while loop till the number of changes made is zero.

This is the most straight-forward answer I can come up with and is pretty lengthy. Surely there may be some other more ingeneous solutions that sorten the code, and the execute time.

[kris.c]

well, i thought of something like that... But ,as I said the problem requires abslutely no repeats and the ith pos must not have the ith number.. I have found that I end up with some repeats when I tried something similar to what u mentioned...
thanks

couldn't you just fill an array with numbers from 1-100.

Then shuffle them inside the array?

[kris.c]

I will try it out and let u know if it works to suit my req..
thanks

Here's what you can do : First, generate 100 random numbers, using rand() function (I think you first have to seed the function with some variable value.)

Now, check for any repeated numbers, or numbers that are on the index same as themselves using recursion; change the number again using another rand() call. keep track of the number of changes made.

Now, repeat the above process using while loop till the number of changes made is zero.

This is the most straight-forward answer I can come up with and is pretty lengthy. Surely there may be some other more ingeneous solutions that sorten the code, and the execute time.

[Rashakil Fol]

What do you mean by 'random'? What is the range of these numbers? If they're numbers from 0 to 99, then you can prefill the array, do a random_shuffle on them, and then go through the array looking for numbers at their own indices. Whenever you get them, swap them with a randomly numbered index (other than itself). Then you're done.

[Narue]

>Now, check for any repeated numbers, or numbers that are on the index
>same as themselves using recursion; change the number again using
>another rand() call. keep track of the number of changes made.
Theoretically, this could be a neverending process. It's also very complicated, and I'm surprised it's the most straightforward answer you could manage. Care to try again? :)

[Exodust]

I think it depend on what range you choose for the random number generation. If it is 1 to 100, then this process will be practically useless. But if the range is of the order of 1 to 1000, then there is a pretty good chance that not more than some milliseconds will be required. Agreed, it is not the best, and I've told that before. By straight-forward, I mean that this algorithm will be the first one to come to mind. Obviously, if it is the first one, it is probably the worst one too. If this question came in my exam, I would have used this algorithm, but not to make a program actually.

@Narue Care to try your hand at the problem youself? Let's see what you come up with.

[Narue]

>@Narue Care to try your hand at the problem youself?
The easiest solution would be to restrict the range to numbers greater than the largest index in the array. That ensures that none of the numbers will match an index. Then you can insert random numbers into a binary search tree until the size reaches 100 to guarantee uniqueness. Copy the numbers into an array using whatever traversal you'd like and you're done. The performance is O(N) and the code is short if the requisite framework is present:

while ( tree.size() < size ) {
  tree.insert ( random_integer ( size, RANDOM_ULIMIT ) );
}
copy ( array, array + size, tree.begin() );

[Exodust]

>@Narue Care to try your hand at the problem youself?
The easiest solution would be to restrict the range to numbers greater than the largest index in the array. That ensures that none of the numbers will match an index. Then you can insert random numbers into a binary search tree until the size reaches 100 to guarantee uniqueness. Copy the numbers into an array using whatever traversal you'd like and you're done. The performance is O(N) and the code is short if the requisite framework is present:

while ( tree.size() < size ) {
  tree.insert ( random_integer ( size, RANDOM_ULIMIT ) );
}
copy ( array, array + size, tree.begin() );

Good answer in my opinion. I've never used trees in a program though I know how to. So, I don't know much about its advantages. But it looks like it will be faster than mine. But you had to think didn't you? :)

[Narue]

>But you had to think didn't you?
Only because lately I haven't been able to think straight. ;)