Generating a list of unique random numbers

[Gr3yling]

So, I've been trying to understand random dungeon generation, and have really gotten sidetracked on a tangent related to generating lists of random numbers.  It's driving me crazy, and I can't go forward with working on making an actual roguelike until I can resolve the questions I have.  Sorry if this question isn't as directly related to programming a roguelike as some of the others on this board, but I know you guys/girls and I think you are my best chance for getting an answer that I can understand.

I want to generate a list of unique random numbers in the following way:

1. generate a random number
2. check to see if it is already in the list
3. if not, append it
4. if so, chunk it and go back to step 2

I *don't* want to do something like this code that I wrote:

from random import randint

random_list = []

random_source_list = [i for i in range(10)]

print random_list

print random_source_list

while len(random_list) <= 9:
    random_index = randint(0, len(random_source_list) - 1)
    random_list.append(random_source_list[random_index])
    random_source_list.remove(random_source_list[random_index])

print random_list

print random_source_list

It works, but I want to be able to accomplish my goal in the way that I stated previously.  Nor do I want to append a random number to the list, check for repeats, and then delete repeating numbers until I get a list of all uniques.  I already came up with a way to do it like that, but it just seems sloppy to me to use trial and error.  And I don't want to use classes either.

I realize these criteria must seem arbitrary, but this is something that I'm trying to figure out as a personal challenge, and it's about to drive me nuts.

[sokol815]

ah, the experiences of lists of random numbers. Javascript makes something like this super easy:

Code: [Select]

var numArr = Array(20);
for(var i = 0; i < numArr.length;i++){
   numArr[i] = i;
}
numArr.sort(function(){return Math.random()-.5;});
console.log(numArr);
some outputs from the above code:

Code: [Select]

[15, 18, 10, 1, 7, 6, 9, 8, 4, 19, 11, 5, 12, 13, 14, 2, 3, 16, 17, 0]
[10, 17, 5, 15, 4, 9, 13, 1, 19, 11, 0, 12, 6, 2, 18, 14, 7, 3, 16, 8]
[19, 2, 3, 4, 5, 6, 8, 7, 13, 11, 0, 9, 1, 14, 15, 16, 17, 12, 10, 18]

the magic here is in the built-in javascript sort function. you can pass it random values and it will randomly sort all the elements.

another option that may be simpler for you (if you don't have an easy way to make sort be random) is to first initialize a new ordered array then create another array and pull from the first randomly and append to the second.

Code: [Select]

var arr = [0,1,2,3,4,5,6,7,8,9];
var endArr = [];
while(arr.length > 0){
     var loc = (Math.random() * arr.length) >> 0; //bitwise operator >> 0 does a shift 0 and gives an int. Math.random() returns a value between 0 and 1.
     endArr.push(arr[loc]); //add the picked element to the destination array.
     arr.splice(loc,1); //remove the just added element from the source array; arr.length is now 1 less.
}

the 2nd way is probably one of the easiest ways to do what you are proposing. Have fun!

[Trystan]

If you don't want to remove duplicates or check if something is a duplicate then you can use a set instead of a list (sets usually ignore any duplicates you try to add) or, if you have a small enough set of acceptable values, actually remove things from the random_source_list when you add to your random_list.

Code: [Select]

while len(random_list)< 10:
  random_list.add(random_source_list.pop(randint(0, len(random_source_list))))

I haven't done python in a long while so the syntax may be off.

[Gr3yling]

the 2nd way is probably one of the easiest ways to do what you are proposing. Have fun!

Thanks for the suggestion, but I *don't* want to pull from one list to add to another.  I already found a way to do that (although it was probably much clumsier than the one you suggested).   And I forgot about using pop like Trystan suggested, that would have simplified the code that I posted.

It just seems "un-pythonic" that there is no way to go through precisely these steps: generate a random number, compare it to all the entries in a list, and then either append it or generate a new one.

Oh well, I guess it can't be done though.  It makes me feel better to know that there wasn't some obvious solution that I missed.  I appreciate the input from both of you.

[requerent]

Code: [Select]

random.sample(range(x), y)
https://docs.python.org/3.5/library/random.html#random.sample

Pythonic enough?





Edit: Pythonic algorithms leverage the standard lib as much as possible. You shouldn't implement algorithms in python, just instructions.

If you want an algorithm, consider something more dynamic than generate->check->append, which has a potentially sun-burning-out run-time (esp in python). If bit-wise/mask solutions frighten you, try generating the numbers in increasing order. Just add a random delta to the previous value. If you need them shuffled also, you can run a shuffling algo in tandem with the number generation without ever needing to the traverse the currently generated list more than once.

[Trystan]

It just seems "un-pythonic" that there is no way to go through precisely these steps: generate a random number, compare it to all the entries in a list, and then either append it or generate a new one.

Oh well, I guess it can't be done though.  It makes me feel better to know that there wasn't some obvious solution that I missed.  I appreciate the input from both of you.

Code: [Select]

while len(random_list) < 10:
  value = get_some_random_value()
  if value not in random_list:
    random_list.add(value)

Your 3 step algorithm is, I believe, just a few lines of python. If I remember correctly, "X not in XS" is valid python but you may have to use a contains method or whatever python lists have.

[chooseusername]

It just seems "un-pythonic" that there is no way to go through precisely these steps: generate a random number, compare it to all the entries in a list, and then either append it or generate a new one.

Oh well, I guess it can't be done though.  It makes me feel better to know that there wasn't some obvious solution that I missed.  I appreciate the input from both of you.

Code: [Select]

while len(random_list) < 10:
  value = get_some_random_value()
  if value not in random_list:
    random_list.add(value)

Your 3 step algorithm is, I believe, just a few lines of python. If I remember correctly, "X not in XS" is valid python but you may have to use a contains method or whatever python lists have.

Or if you use sets:

Code: [Select]

MY_SET = set()
while len(MY_SET) < 10:
   MY_SET.add(get_some_random_value())


[requerent]

OMG PEOPLE STOP!

https://docs.python.org/3.5/library/random.html#random.sample

THERE IS A FUNCTION IN THE PYTHON STD FOR THIS EXACTLY.

[mushroom patch]

Obviously, you should just use the standard library functions that perform sampling (random.sample) without replacement from a collection or random permutation of a list (random.shuffle, although the implementation of this method sounds like it would not be suitable for purposes that require even moderately high performance).

If it bugs you that you don't know a good way to do it by hand, it sounds like for what you want to do, you could just make a list of the values you want to draw from, say there are n of them, select a random number k between 1 and n and take the kth element of the list, removing that element when you do so and putting into your result list. Decrement n and repeat until you've populated your list. In other words, what you're asking for is sampling without replacement. Since it takes time check if something is already in your list, this method will be asymptotically better than what you suggest in the OP.

[Jaxian]

Even though there is a built-in function, we might still want to understand how this can be implemented.  Learning this algorithm will help us apply apply a similar technique to solve other problems.

I unfortunately don't know Python, but I will attempt to write Python code here using a reference, so forgive the almost-certainly-incorrect syntax.  To write your algorithm as you described it in the original post, it might look like this:

Code: [Select]

value_list = list()

for x in range(0, 100):
    val = random()
   
    while val in value_list:
        val = random()

    value_list.append(val)

However, the line "val in value_list" requires the code to compare "val" to every single value in the list.  As the list grows in size, this could take a longer time.  For this reason, it is better to use a Set instead of a List.  A Set uses hashing so that the same operation can be completed much more quickly:

Code: [Select]

used_values = set()

for x in range(0, 100):
    val = random()

    while val in used_values:
        val = random()

    used_values.add(val)

    // Do something with val, maybe append to a result list or call a function to build part of your map

In the code from your original post, you started with a known list of possible values (random_source_list).  If you have such a list, you could write an algorithm that randomly picks a value from that list, then swaps the value at the end into the spot you picked.  Then the next time you pick a number, you consider the list one position shorter.  This would be fast, but will modify the source list, meaning you might have to copy it if you need it somewhere else.  That might look like this:

Code: [Select]

len = len(source_list)

for x in range(0, 100):
    val_index = _int(random() * len)
    val = source_list[val_index];
    source_list[val_index] = source_list[len - 1]
    len--

    // Do something with val, maybe append to a result list or call a function to build part of your map

As requerent wrote, it makes the most sense to use the built-in version random.sample method to solve this problem, but hopefully these examples were useful in some way.

[Gr3yling]

Even though there is a built-in function, we might still want to understand how this can be implemented.  Learning this algorithm will help us apply apply a similar technique to solve other problems.

Thanks Jaxian.  Yep, that's exactly where I was going with this.  Although I do appreciate your input, requerent.

I think for the most part I understand what you guys are saying, and I'll try some of your suggestions. 

EDIT: Oh, and maybe in about a decade I'll have a working prototype to share with you all.

[requerent]

Even though there is a built-in function, we might still want to understand how this can be implemented.  Learning this algorithm will help us apply apply a similar technique to solve other problems.

Thanks Jaxian.  Yep, that's exactly where I was going with this.  Although I do appreciate your input, requerent.

I think for the most part I understand what you guys are saying, and I'll try some of your suggestions. 

EDIT: Oh, and maybe in about a decade I'll have a working prototype to share with you all.

sorry. All I was trying to say is that if the algorithm isn't O(N), it's no good.

[Xecutor]

The question is in what range you want your random numbers?
Answer for 'n random numbers in range 0..n-1' would be classic algorithm by Knuth:

Code: [Select]

  arr=Array(n)
  for i in 0..n-1
   k=random_in_range(0..i)
   arr[i]=arr[k]
   arr[k]=i
  end

if you want n random numbers in arbitrary range, then variant with set above is probably the best option.
if you want content of an array in random order, generate array of random indeces with algo above and
use them to access array of items.

[chooseusername]

However, the line "val in value_list" requires the code to compare "val" to every single value in the list.  As the list grows in size, this could take a longer time.  For this reason, it is better to use a Set instead of a List.  A Set uses hashing so that the same operation can be completed much more quickly:

Code: [Select]

used_values = set()

for x in range(0, 100):
    val = random()

    while val in used_values:
        val = random()

    used_values.add(val)

    // Do something with val, maybe append to a result list or call a function to build part of your map


Note that for every number generated, val is looked up in used_values twice.  Once to check if it is in there already, and once when it gets added (because that's how sets work).  If you take this into account, you can reduce this example to what I wrote earlier.  Of course, you are not talking about Python's random.random() here, that would be bad.

It is not premature optimisation, it is understanding exactly how things work, and writing code so as to not do unnecessary work.  These things do matter, I've often profiled slow Python code in commercial Python games, and these things make a significant difference.

random.sample() is a limited function, and it smacks to me of something someone put in to handle their own special case.  The Python standard library has many of these sorts of things.  There are arbitrary modules in there that almost do what I want, but are just unusable because whomever wrote them wanted them to work in a way that was unusable for me.  Back to sample(), I've never had a sequence I needed to pick out a unique list of entries from.  If I had to do this, it would be clearer IMO to write the code yourself than to call this function.  Most of my random number usage was picking from weighted lists, and repicking was desirable.  After all, you want 2x50 arrows sometimes, 1x50 arrows some other times, and so forth.

[mushroom patch]

random.sample() is a limited function, and it smacks to me of something someone put in to handle their own special case.  The Python standard library has many of these sorts of things.  There are arbitrary modules in there that almost do what I want, but are just unusable because whomever wrote them wanted them to work in a way that was unusable for me.  Back to sample(), I've never had a sequence I needed to pick out a unique list of entries from.  If I had to do this, it would be clearer IMO to write the code yourself than to call this function.  Most of my random number usage was picking from weighted lists, and repicking was desirable.  After all, you want 2x50 arrows sometimes, 1x50 arrows some other times, and so forth.

Sampling without replacement is an extremely standard thing to do. It appears in any book on basic probability. If you want to draw a hand of cards from a deck in a card game, your deck may be represented by a list and the hand can be "drawn" via random.sample(). One can imagine plenty of similar applications. I've never felt this way about the standard library in python myself, but I suppose everyone has an opinion. I can hardly believe you think this is an instance of implementing something no one else is likely to use/need though.

Edit: Perhaps a more topical example: Suppose you want to generate treasures to populate a vault, but you don't want a lot of repeated treasures or treasure types and you want to do it in a flexible, data-oriented way (e.g. you want it to depend on dungeon levels, maybe some kind of theming for different vault types, etc.). You can write a routine that puts together a large list of item types (or better item builder objects), then use random.sample to draw from it.