3

I would like to generate random numbers in the range (0..."MAX"). I would like to make a loop such that every time going through the loop a new unique random number is generated (should not repeat). The loop will continue a total of "MAX" times. There should be "MAX" number of random numbers generated in total. When sorted, the values should be 0..."MAX"; no repetition.

Restrictions: - Assume MAX is much larger than int. (no memory to store all number permutations in memory)

My proposed solution: If I seed the generator from 0...MAX would that allow me to print every unique number between 0 and MAX as in the below function? Assume there's no space to store all numbers and shuffling them.

for x in range (0, MAX):
    random.seed(x)
    num=random.randint(0, MAX)
    print("seed = ",x, "    random number = ", num)

If the answer for the above is yes then would this generation be reversible (can i get the seed from the random number)? In which case would this be considered a kind of block cipher that is if the seed (key) and the range is the same length?

Improve this question
8
  • 2
    Can you explain what output you want? Your code is invalid because randint requires arguments. Also, nothing in your code will prevent repetitions. Why are you seeding the generator anew on each iteration? Commented Feb 13, 2014 at 4:03
  • Tnx. Fixed. I want a new random number in the range of 0...Max for each iteration and it must not repeat with previous numbers. I'm seeding it because i'm guessing that a unique seed means a unique number for the first iteration of the PRG but I don't know what is the max seed the prg would take before repeating. Assume there's no memory to store all the numbers. Commented Feb 13, 2014 at 4:11
  • 2
    "considered a kind of block cipher" - if you're planning to use this for any sort of cryptographic purpose, don't. Commented Feb 13, 2014 at 4:11
  • just using it to generate non repeating random but curious if it fit the description for a block cipher. Commented Feb 13, 2014 at 4:15
  • What requirements do you have for "randomness"? Does it have to be good enough for simulations? Cryptography? Does it just need to be nonrepeating? How big is MAX? Commented Feb 13, 2014 at 4:18

3 Answers 3

Reset to default
1

The random module has a sample function, which is predicated on producing unique elements. It is used as in the following example:

random_list = random.sample(xrange(10000000), 60) 
# generates a list of 60 random numbers in the 
# range 0 to 10000000 without repetition

But, do be aware that it will throw an exception if the length of the list is greater than the size of the population, e.g. 

random_list = random.sample(xrange(5), 60 # you will get a ValueError here
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

"do be aware that it will repeat if the length of the list is greater than the size of the population" - no it won't. It'll raise a ValueError. Why did you think it would repeat?
Also, you can't sample from 5.
@user1144251 You are looking for the random.shuffle, like I have shown in my answer.
This works fine for a small set. But for a large number it won't work ie: random.sample(range(78364164095),78364164095)
1

You can do like this:

input = set()
for i in range(MAX):
    input.add(random.randrange(x,y))
print input

with in the range of x and y it will select some random values. W/o repetition means you can use set. so i am adding those values to set.

just make a try this one.

Improve this answer

Comments

0

If you want to get all the numbers within a particular range,

  1. either we have to store the generated random numbers and compare them against the newly generated random number

    import random
result = []

# hash values of numbers between -5 to 256 are the same as the
# numbers themselves. So, whatever may be the order, set will have them
# in the sorted order. So, `result` cannot be a `set` here.

for x in range (0, 10):
    num = random.randint(0, 10)
    while num in result:
        num = random.randint(0, 10)
    result.append(num)
print result

  2. or we can generate the list and shuffle it like this

    data = range(10)
import random
random.shuffle(data)
print data

    since you already have the population as a list and random.shuffle is an in-place operation, the result doesn't have to be stored in a separate list.

Improve this answer

8 Comments

assume that there's not enough memory to store everything in memory.
@user1144251 Then how are you going to generate the random numbers and store it?
First way should use set, not list. List (vector) needs O(N) time to find if it has an item, while for hash-based set it's O(1) (on average).
@SergeyDymchenko hash values of numbers between -5 to 256 are the same as the numbers themselves. So, whatever may be the order, set will have them in the sorted order. So, we cannot use set here.
not storing the random number just printing it out (streaming it) no storage.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.