1

I want to create a function in C. It will return a random integer in-range of N like:- rand() % N; but the thing is I want to keep track of uniqueness. I don't want the numbers to repeat. but i can also do this by making an array and copying the generated integers in it. like :- array[count] = rand() % N; and check every time if the number generated was already inside it or not. (simply by searching it inside the array[]); this is a simple approach but a correct one. it will take many if's and for's; for this to work. this is the best i can come up with.

The thing is, I want to get the best possible/optimized solution for this problem. What will be the most efficient way to do this?

lets clear some things:- i want to set some text in a UILabel from a NSArray that is always unique. my NSArray is getting data from a Plist, and my Plist has over 1000 entries. if i want to do this many times it will effect the performance so i want some efficient way to do this.

Abizern
  • 146,289
  • 39
  • 203
  • 257
SAQIBZAFAR
  • 89
  • 2
  • 10
  • 4
    if it guarantee there is no repetition is no more random, isn't this from logic ? – Felice Pollano Dec 18 '11 at 19:47
  • 1
    "Random" and "unique" in the same sentence do not belong. What exactly is the problem you are trying to solve? – Jon Dec 18 '11 at 19:47
  • lets say i am trying to fill an array with random numbers upto ceil of 100, or another example for iphone dev is that i am showing random Objects in a label from a NSArray of 1000 objects. – SAQIBZAFAR Dec 18 '11 at 19:50
  • 4
    @user: What you are trying to do is efficiently *shuffle* a set of numbers. This has been discussed *many* time in various contexts. – dmckee --- ex-moderator kitten Dec 18 '11 at 19:52

5 Answers5

6

It sounds like what you want is really a random permutation of the number 1..N. So, fill an array with consecutive integers 1..N and then shuffle the array. There are well known algorithms for shuffling that you can look up.

Caleb
  • 124,013
  • 19
  • 183
  • 272
1

Use some sort of hash table to store the already generated number and to fast check the number is already seen. I don't know exacltly what you are trying to do, but since you are requiring unique rand, I guess you are trying to permutate a finite set, if it is the case, have a look at some Shuffling Algorithms.

Felice Pollano
  • 32,832
  • 9
  • 75
  • 115
1

Rather than an array, you could use a super fast an efficient bloom filter. If you are generating any large quantity of numbers, this will be WAY faster than looping through an array.

Alex Wayne
  • 178,991
  • 47
  • 309
  • 337
  • thanks, do i have to design it for iphone or is there a class that implements it for me, and i can use it directly? – SAQIBZAFAR Dec 18 '11 at 19:57
  • Apple provides no such construct. Though there are likely libraries out there somewhere you can use. I've never used one myself, so can't advise much more. – Alex Wayne Dec 18 '11 at 20:35
1

Four options, all of which are O(1) in both memory and time:

  1. Just increment a global counter. Since you want uniqueness, you can't generate random numbers anyway.
  2. Generate a number from a set sufficiently large that it is highly improbable that a number repeats. 64 bits is sufficient for in-app uniqueness; 128 bits is sufficient for global uniqueness. This is how UUIDs work.
  3. If option 1 isn't "random" enough for you, use the CRC-32 hash of said global (32-bit) counter. There is a 1-to-1 mapping (bijection) between N-bit integers and their CRC-N so uniqueness will still be guaranteed.
  4. Generate numbers using a Linear Feedback Shift Register. These are N-bit counters which count in a seemingly "random" (though obviously deterministic) pattern. For your purposes, this would essentially be a modestly faster version of option 3.
Chris Pacejo
  • 2,817
  • 4
  • 17
  • 17
0

The algorithm described is pretty bad because it searches through the new array for each new entry. This means it has to search through more and more data as the array grows, and worse, as the number of remaining item decreases, it will end up looping more.

For example, if you have a list from 1…10, when you have filled eight items, there are only two items left (say, 7 and 9), now, each time you generate a random number, it will generate a non-unique number 80% of the time, and have to scan through at least six entries before detecting the duplicate.

There’s probably some even better methods in some libraries, but a better way than the one in the question would be to create a (linked) list of items, pick one at random, remove it, and add it to the new list. That way, every time you pick one a random one, it is guaranteed to be unique because the used ones are no longer in the pool.

Synetech
  • 9,643
  • 9
  • 64
  • 96