#1
  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?

    thanks in advance
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    Start with this
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Location
    Iran
    Posts
    149
    Rep Power
    139
    Maybe the following could help

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


    Regards,
    Dariyoosh
  6. #4
  7. 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
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,841
    Rep Power
    480
    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]

    Comments on this post

    • codergeek42 agrees : Particularly useful for the BogoSort algorithm :)
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1802
    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 12:24 PM.
  12. #7
  13. 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?
  14. #8
  15. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1802
    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 02:20 PM.

IMN logo majestic logo threadwatch logo seochat tools logo