Member Avatar for lrh9

I always wondered how a programmer could efficiently generate a random number from a set* of numbers once and only once.

I quickly realized the inefficient solution. Simply generate the number and if it equals one you have all ready generated then regenerate the number.

Regenerating the number is a poor method. Especially in a small set or if you are going to exhaust the elements in the set.

Today I realized a smarter solution. Instead of using random to generate a number that is in the set, use random to generate the index of a element in the set and then return that value and remove the element from the set.

Now I'm just wondering what the best way to implement this is.

It would be relatively simple to implement it in a function, but part of the procedure is modifying the list in question. Python documentation labels modifying lists within a function as a bad practice. I just don't understand why. I also can't understand how to get around this either at the moment.

* By set, I don't necessarily mean Python's built in set object. This would probably be implemented using a mutable sequence.

Edited by lrh9 because: n/a
  • 2 Contributors
  • 13 Replies
  • 394 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by lrh9

Dani AI

Generated

Good thread — the tradeoffs are mainly performance, whether you want to mutate the original sequence, and whether you need cryptographic randomness.

  • Conceptually simple / safe choices

    • Use the standard tools: random.shuffle (in-place Fisher–Yates) or random.sample (non‑destructive sampling). Both give you unbiased selection when used correctly; sample is convenient if you want k unique items without modifying the original sequence. (git.joshthomas.dev)

  • When not to use repeated regenerate-or-retry or repeated random-index pop

    • Popping an arbitrary index repeatedly (the approach suggested) is fine for small lists, but list.pop(i) (with i not at the end) shifts elements and is O(n), so doing that N times becomes O(n^2). For larger N that is slower than a single shuffle + linear scan. If you need constant-time removals from the ends, use collections.deque. (digitalocean.com)

  • Practical recommendations (based on your intended use)

    • To return every item exactly once (destructive): shuffle in-place and iterate, or call random.sample(seq, len(seq)) to get a shuffled copy if you must keep the original. Both are O(n) and avoid the quadratic cost of many mid-list pops. (git.joshthomas.dev)
    • To draw k ≪ n items without replacement: use random.sample(seq, k) — it’s implemented efficiently and works with range() in a memory‑efficient way. (jacobcoffee.github.io)
    • For streaming data (you can’t hold the whole sequence), use reservoir sampling (Algorithm R) to get k uniform samples in one pass.

  • About PRNG quality and popitem

    • Python’s random uses the Mersenne Twister (period 2**19937−1); that’s enormous and fine for simulations/games/sampling, but not for cryptographic uses — use random.SystemRandom or the secrets module for security. Also, CPython’s shuffle is the standard (correct) Fisher–Yates implementation, so prefer it over ad‑hoc shuffles. (docs.python.org)
    • dict.popitem() removes and returns a (key,value) pair. Since Python 3.7 dicts preserve insertion order, popitem() now removes the last-inserted pair (LIFO); it is not a random selector and should not be used as one. (This matches ’s note.) (docs.python.org)

Finally: mutating an input list inside a function is fine when intended, but document the side effect (or operate on a copy) — and avoid mutable default arguments. The Python tutorial covers these gotchas and the recommended patterns. (docs.python.org)

Recommended Answers

All 13 Replies

Member Avatar for lrh9

Actually, it would probably be better to create a new class that inherits another sequence. This might allow this new object to use all of the old methods of the inherited object and have a new method for returning and removing a element of the sequence.

Member Avatar for Gribouillis

Why don't you just use shuffle ?

from random import shuffle

def random_unique(sequence):
    L = list(sequence)
    shuffle(L)
    return iter(L)

for x in random_unique(range(10)):
    print(x)
Member Avatar for lrh9

Why don't you just use shuffle ?

from random import shuffle

def random_unique(sequence):
    L = list(sequence)
    shuffle(L)
    return iter(L)

for x in random_unique(range(10)):
    print(x)

There are more permutations for a sequence than there are indexes in a sequence. The total number of permutations for even a small sequence can exceed the period of most random number generators. While this probably has little impact for a person merely seeking to rearrange a sequence in place, when you want to obtain only one value each value in the sequence would not have an equally probable chance of being at the point which you sample the resulting permutation.

Member Avatar for Gribouillis

I don't understand the argument. If you succeed in writing your random generator differently, it will be an alternative to shuffle. Can you explain more precisely the probabilistic argument ? I think that with shuffle, each item has the same probability to be at a given position in the generated sequence.

Member Avatar for lrh9

I don't understand the argument. If you succeed in writing your random generator differently, it will be an alternative to shuffle. Can you explain more precisely the probabilistic argument ? I think that with shuffle, each item has the same probability to be at a given position in the generated sequence.

Because the number of permutations exceeds the period of the random number generator, some sequences will never be returned by the function.

Member Avatar for Gribouillis

Because the number of permutations exceeds the period of the random number generator, some sequences will never be returned by the function.

I still don't agree. It's very easy to write a shuffle function

from random import randrange

def my_shuffle(the_list):
    n = len(the_list)
    while n > 1:
        i = randrange(n)
        the_list[i], the_list[n-1] = the_list[n-1], the_list[i]
        n -= 1

L = range(10)
my_shuffle(L)
print(L)

Shuffle generates only one permutation. Now since each permutation of n objects is the product of at most n transpositions, you only need to generate at most n random transpositions in a set of order O(n^2) possible transpositions.

Edited by Gribouillis because: n/a
Member Avatar for lrh9

I still don't agree. It's very easy to write a shuffle function

from random import randrange

def my_shuffle(the_list):
    n = len(the_list)
    while n > 1:
        i = randrange(n)
        the_list[i], the_list[n-1] = the_list[n-1], the_list[i]
        n -= 1

L = range(10)
my_shuffle(L)
print(L)

Shuffle generates only one permutation. Now since each permutation of n objects is the product of at most n transpositions, you only need to generate at most n random transpositions in a set of order O(n^2) possible transpositions.

So what you're saying is that as the number of permutations exceeds the period of Python's random number generator, each index has an equally probable chance of being relocated to the beginning? Can you prove this?

Member Avatar for Gribouillis

So what you're saying is that as the number of permutations exceeds the period of Python's random number generator, each index has an equally probable chance of being relocated to the beginning? Can you prove this?

I think I understand your point now. There must be a limitation somewhere when n is large. However, note that the builtin shuffle function takes an optional argument 'random' which allows you to pass your own random generator. So I still believe that the best method is to use shuffle, but for large n, write your own random generator with a larger period. An interesting point would be to have an order of magnitude of the n for which this problem arises.

Member Avatar for lrh9

It confuses me. I've never had to understand random number generation and pseudo random number generation before. I might be wrong and you might be right. There might be nothing mathematically wrong with shuffle.

However, I do think it is a fair idea that given two options for accomplishing something, it is probably better to use the option that is conceptually simpler if you have trouble understanding the more complex one or if you have trouble understanding both.

Of course, after reviewing the list object, I think the point might be moot. If your goal is to obtain a random element from a list and then remove it, then it would be simplest to use the list.pop(index) method where index is a randomly generated number.

*Smacks forehead.*

Member Avatar for lrh9

Here's what I came up with.

#!/usr/bin/env python

import random

class pool(list):
    
    def rand_index(self):
        length = len(self)
        return random.randint(0, length - 1)

    def unique_rand(self):
        return self.pop(self.rand_index())

def main():
    print("""Prints each element in a sequence at random once and only once.""")
    my_pool = pool("AaBbCcDd")
    print(my_pool.unique_rand())
    print(my_pool.unique_rand())
    print(my_pool.unique_rand())
    print(my_pool.unique_rand())
    print(my_pool.unique_rand())
    print(my_pool.unique_rand())
    print(my_pool.unique_rand())
    print(my_pool.unique_rand())
    try:
        print(my_pool.unique_rand())
    except:
        print("The ninth attempt failed because it attempted to remove a ninth element from a sequence of eight elements that had eight previous removals.")
    
    
if __name__ == "__main__":
    main()
Member Avatar for lrh9

Actually, dictionaries have a popitem method that returns an arbitrary key and value.

I don't know how much a difference there is to using my method or a dictionary though.

Member Avatar for Gribouillis

Actually, dictionaries have a popitem method that returns an arbitrary key and value.

I don't know how much a difference there is to using my method or a dictionary though.

Popitem is not meant to be a random generator.

Member Avatar for lrh9

Popitem is not meant to be a random generator.

What does it do then? How is it used?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.