### Thread: Generating number without repetition

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
11
Rep Power
0

#### Generating number without repetition

assuming the function is generate key, I want to store the numbers in an array, the size of the array depends on a predefined variable "size", so here's the function

srand(time (NULL));
for (i = ; i < size; i++){
array[i] = rand()%size;
}

i tried putting if statements do another loop but it's just not working, anyone can chime in?

for (i = 0 ; i < size; i++) array[i] = i;

Then shuffle the array:
Pick random x and y indices in the array, and swap the two elements.
3. Maybe the following could help

http://stackoverflow.com/questions/5064379/generating-unique-random-numbers-in-c

Regards,
Dariyoosh
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
11
Rep Power
0
sorry I should have mentioned i'd need the numbers to be shuffled that's why I used rand.

doing array[i] = i will just give me a list of numbers of ascending order not shuffled

and I don't want to get an ascending list and shuffle it, I want to use the rand command. I'm working on an assignment and I have to use it
5. Salem's method has the advantage that it cheaply (little resources) meets your headline requirement "Generating number without repetition".

Fisher-Yates shuffle
Originally Posted by wikipedia
To shuffle an array a of n elements (indices 0..n-1):
Code:
```  for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]```

• codergeek42 agrees : Particularly useful for the BogoSort algorithm :)
6. Originally Posted by maans88
sorry I should have mentioned i'd need the numbers to be shuffled that's why I used rand.
[...]
I don't want to get an ascending list and shuffle it, I want to use the rand command. I'm working on an assignment and I have to use it
Indeed the rand() function will be useful in shuffling.

It is inefficient to try this in one step as you suggest. After size - 1 numbers, there would only be one acceptable value remaining, and it would take rand() a non deterministic length of time to return it, given a sufficiently bad rand() implementation, and large valie of size it may never complete.

You might try the following algorithm, it is at least bounded in its execution time.

Code:
```1) Create an array, initialise all values to -1 (indicating empty - use memset() for this)
2) For each n from 0 to size -1...
3)   pick a random number i from 0 to size -1
4)   while array[n] != -1
5)      n = (n + 1) % size
7)   wend
8)   array[n] = i
9 endfor```
That way deterministic values i are placed at random positions in array, using the -1 "empty" value to find the first empty position after the random index (with wrap-around). The worst case will be that you select a location one after the last available location so that the while loop wraps all the war around.

Note that selecting a random range using rand() % size is somewhat less than random since it introduces bias that can be significant for large values of size relative to RAND_MAX that are not an integer power of two. The following is a better solution:

Code:
`i = (int)((double)rand() / (double)RAND_MAX) * size ;`
Last edited by clifford; February 16th, 2013 at 01:24 PM.
7. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2013
Posts
11
Rep Power
0
one of my friends did it using a while loop and and a for loop inside it.

the outter loop is the while loop and the inner is teh for loop

any idea?
8. Originally Posted by maans88
one of my friends did it using a while loop and and a for loop inside it.

the outter loop is the while loop and the inner is teh for loop

any idea?
If your friend does not think that it is fair to reveal his algorithm, then why would it be more fair for complete strangers to do so!? He's your friend - you ask him.

Pretty much any algorithm will involve nested loops one way or another so knowing merely that your friend used a for and a while in a particular order does little to reveal his solution. Moreover in C any while loop can be implemented as a for loop, and any for loop as a while loop, so the particular loop used reveals nothing. You could even implement a loop using goto (don't by the way), so it tells us nothing.

Besides I gave you a usable algorithm what's wrong with that? It would be far better for you to submit a solution that at least looked like you came up with it. Whatever you choose to do, do make sure that you understand the solution, you may be asked to explain it to your tutor.
Last edited by clifford; February 16th, 2013 at 03:20 PM.