How do you use random without repetition in python?

Linear Congruential Pseudo-random Number Generator

O(1) Memory

Nội dung chính Show

• Linear Congruential Pseudo-random Number Generator
• Sample Results
• Using random.sample() example 1:
• Using random.choices() example 3:
• How do you generate a random number without repeating it in Python?
• How can I generate random number without duplicates?
• How do you do random sampling without replacement in Python?
• How do you select a random element from a list without repetition in Python?

O(k) Operations

This problem can be solved with a simple Linear Congruential Generator. This requires constant memory overhead (8 integers) and at most 2*(sequence length) computations.

All other solutions use more memory and more compute! If you only need a few random sequences, this method will be significantly cheaper. For ranges of size N, if you want to generate on the order of N unique k-sequences or more, I recommend the accepted solution using the builtin methods random.sample(range(N),k) as this has been optimized in python for speed.

Code

# Return a randomized "range" using a Linear Congruential Generator
# to produce the number sequence. Parameters are the same as for 
# python builtin "range".
#   Memory  -- storage for 8 integers, regardless of parameters.
#   Compute -- at most 2*"maximum" steps required to generate sequence.
#
def random_range(start, stop=None, step=None):
    import random, math
    # Set a default values the same way "range" does.
    if (stop == None): start, stop = 0, start
    if (step == None): step = 1
    # Use a mapping to convert a standard range into the desired range.
    mapping = lambda i: (i*step) + start
    # Compute the number of numbers in this range.
    maximum = (stop - start) // step
    # Seed range with a random integer.
    value = random.randint(0,maximum)
    # 
    # Construct an offset, multiplier, and modulus for a linear
    # congruential generator. These generators are cyclic and
    # non-repeating when they maintain the properties:
    # 
    #   1) "modulus" and "offset" are relatively prime.
    #   2) ["multiplier" - 1] is divisible by all prime factors of "modulus".
    #   3) ["multiplier" - 1] is divisible by 4 if "modulus" is divisible by 4.
    # 
    offset = random.randint(0,maximum) * 2 + 1      # Pick a random odd-valued offset.
    multiplier = 4*(maximum//4) + 1                 # Pick a multiplier 1 greater than a multiple of 4.
    modulus = int(2**math.ceil(math.log2(maximum))) # Pick a modulus just big enough to generate all numbers (power of 2).
    # Track how many random numbers have been returned.
    found = 0
    while found < maximum:
        # If this is a valid value, yield it in generator fashion.
        if value < maximum:
            found += 1
            yield mapping(value)
        # Calculate the next value in the sequence.
        value = (value*multiplier + offset) % modulus

Usage

The usage of this function "random_range" is the same as for any generator (like "range"). An example:

# Show off random range.
print()
for v in range(3,6):
    v = 2**v
    l = list(random_range(v))
    print("Need",v,"found",len(set(l)),"(min,max)",(min(l),max(l)))
    print("",l)
    print()

Sample Results

Required 8 cycles to generate a sequence of 8 values.
Need 8 found 8 (min,max) (0, 7)
 [1, 0, 7, 6, 5, 4, 3, 2]

Required 16 cycles to generate a sequence of 9 values.
Need 9 found 9 (min,max) (0, 8)
 [3, 5, 8, 7, 2, 6, 0, 1, 4]

Required 16 cycles to generate a sequence of 16 values.
Need 16 found 16 (min,max) (0, 15)
 [5, 14, 11, 8, 3, 2, 13, 1, 0, 6, 9, 4, 7, 12, 10, 15]

Required 32 cycles to generate a sequence of 17 values.
Need 17 found 17 (min,max) (0, 16)
 [12, 6, 16, 15, 10, 3, 14, 5, 11, 13, 0, 1, 4, 8, 7, 2, ...]

Required 32 cycles to generate a sequence of 32 values.
Need 32 found 32 (min,max) (0, 31)
 [19, 15, 1, 6, 10, 7, 0, 28, 23, 24, 31, 17, 22, 20, 9, ...]

Required 64 cycles to generate a sequence of 33 values.
Need 33 found 33 (min,max) (0, 32)
 [11, 13, 0, 8, 2, 9, 27, 6, 29, 16, 15, 10, 3, 14, 5, 24, ...]

In this tutorial, we will learn how to get non-repeating random numbers in Python. There is no in-built function to perform this task. But, we can use some techniques to do this. We will discuss these methods in this tutorial.

Methods we use in this tutorial:

• random.sample()
• ramdom.choices()

These two methods take a list as input and select k(input) random elements and return them back. To get non-repeating elements we give a list as input where there are no repeating elements. Even if we already have a list with repeating elements we can convert it to set and back to list this will remove repeating elements. If we don’t have a list and get elements between two numbers we can do that using the range() function.

Let’s look into examples:

Using random.sample() example 1:

random.sample() is an in-built function of Python that gives us a list of random elements from the input list.

#importing required libraries
import random
li=[10,20,30,40,20,30,60,50,60]
#converting list to set so that to remove repeating elements
se=set(li)
li=list(se)
#we use this list to get non-repeating elemets
print(random.sample(li,3))

[60, 50, 20]

Example 2:

Using range() function. This function gives a list of non-repeating elements between a range of elements.

#importing required libraries
import random
li=range(0,100)
#we use this list to get non-repeating elemets
print(random.sample(li,3))

[35, 81, 47]

Using random.choices() example 3:

random.choices() is an in-built function in Python. This method takes 2 arguments a list and an integer. This returns a list of a given length that is selected randomly from the given list.

#importing required libraries
import random
li=[10,20,30,40,20,30,60,50,60]
#converting list to set so that to remove repeating elements
se=set(li)
li=list(se)
#we use this list to get non-repeating elemets
print(random.choices(li,k=3))

[50, 10, 60]

Example 4:

#importing required libraries
import random
li=range(0,100)
#we use this list to get non-repeating elemets
print(random.choices(li,k=3))

[21, 81, 49]

Also read:

How do you generate a random number without repeating it in Python?

How can I generate random number without duplicates?

How do you do random sampling without replacement in Python?

How do you select a random element from a list without repetition in Python?