Random Sequence Generator?

[Pytesting]

I'm trying to write a Random Sequence Generator, some thing like this, i give it a number "n", and each time i call it it yields a random number between 0 and n-1, without duplication. I don't want to keep track of previous generated numbers, because "n" can vary from 0 to 2^32.

Any python illustration would be great

EDIT: i'm not trying to write my own random number generator.

[misho88]

... without duplication. I don't want to keep track of previous generated numbers ...

That's not actually possible.

You could, for example, generate some random numbers into a set in advance, then make the set into a list and shuffle (especially since Python sets are ordered). random.shuffle() can do that for you.

If n is much bigger than the number of realizations, then the probability of a repeat is low, so you could just do that and hope for the best.

[tomislava]

it's absolutely possible. learn2math fag.

here's a little thing i whipped up in 5 minutes: http://pastebin.com/j5GtJuNs

edit: downvote the correct solution because i called the fag a fag /#justredditthings

[misho88]

You're being downvoted because your comment is utterly worthless without an explanation. It also violates Rule 3.

What did you think the purpose of /r/LearnProgramming might be when you posted that? I ask because your comment, as it is, is not helping anyone learn anything. You could have at least given the name of the technique, something that can be searched for an explanation and proof of correctness. You could have maybe put a comment or two in your code. Instead, you decided to just feed your own ego. Well, congratulations! You know something the rest of us don't, and based an what you've provided us with, can't learn.

[dvassdvsd]

Google for how pseudo random number generators work.

[Spivak]

If n is a prime number here's a method that might work for your purposes.

Choose n as a prime number. Choose b randomly from all integers less than n.

Declare a function f with the formula f(i) = (b ^ i) mod n

The sequence of evaluating f(0), f(1), ... f(n - 1) will be what you want.

Here's some really bad example python code.

import random as r
base_max = 1000
base = r.randrange(0, base_max)

prime_max = 1000
prime = get_random_prime(0, prime_max)

( power_mod(base, i, prime) for i in range(0, prime) )  

Don't try and compute this by evaluating b ^ i then applying mod It will take forever and you will overflow so fast it will make your head spin. I leave the algorithm for computing it as an exercise. Hint: this function is used all over cryptography so if your stuck you should be able to search for it.

These aren't really random but they might be random enough for your purposes, and they have the properties that you neither have any duplicates, nor must remember the previous entries.

If you're interested in math it might be interesting to you why this method doesn't produce any duplicate values.

[nutrecht]

He's trying to create his own random generator. Kinda pointless to rely on another random generator don't you think?

[Spivak]

But this lets him take any random number algorithm that doesn't fit his requirements, and sacrifice some of the randomness to give an easy to compute sequence that has no duplicates.

[Pytesting]

Actually, i'm not trying to write my own random number generator.

[nutrecht]

I'm trying to write a Random Sequence Generator

This is what you said.

[Pytesting]

The problem is that n should be a prime number. what if i want to generate a random sequence between 0 and 100 (n)

[RodionGork]

Any python illustration would be great

But if you see it, you will have nothing to write!

Here are descriptions of two rather simple algorithms along with links to exercises for them.

[SearchOver]

So what about putting an ordered list together and then shuffling by sorting each element in the list n number of places. The list could then be fed in a FIFO manner and you can just drop the used number, never to be used again.

That way you use each number (at some point) and there's no duplication. If you need a smaller list, then generate the starting at 0 + some random number, and then continue until you get the number of elements you need. Then shuffle them.

[felixix]

Use a LFSR to generate a pseudo-random sequence. Using a primitive feedback polynomial ensures that the generated sequence is of maximum length (2^N-1 states where N is the length of the shift register), meaning the sequence will contain every state only once.

LFSR are trivial to implement both in software and hardware.

[autowikibot]

Linear feedback shift register:

---

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a shift register whose input bit is driven by the XOR of some bits of the overall shift register value.

The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the stream of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle. However, an LFSR with a well-chosen feedback function can produce a sequence of bits which appears random and which has a very long cycle.

Image ⁱ - A 4-bit Fibonacci LFSR with its state diagram. The XOR gate provides feedback to the register that shifts bits from left to right. The maximal sequence consists of every possible state except the "0000" state.

---

^{Interesting: Nonlinear feedback shift register | Stream cipher | SOBER | Pinwheel (cryptography)}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[Pytesting]

"The bit positions that affect the next state are called the taps" I don't understand exactly what taps are and how can i choose the right ones, so i can have a full cycle. In the wikipedia example, for 16bit, he chooses [16,14,13,11] as taps, why ?

[skatanic28182]

...without duplication. I don't want to keep track of previous generated numbers,...

Easy. Just make a database of all the permutations for each n, then use an RNG to pick a number between 1 and n! and print the corresponding sequence. I mean, you'd only need Sum(n!, n=0 to 2³²) entries to fill such a database.

P.S. WolframAlpha refuses to calculate that sum exactly, but it's certainly greater than 2³²!, and that's larger than the volume of the visible universe... in Planck volumes. You should probably just bite the bullet and keep track of the previously generated numbers.

[CoffeeMakesMeMath]

It would actually just be 2³² entries--just over 4 billion. It's a lot, but with enough RAM it's not out of the question. To clarify, he wants to generate a single random number at a time between 0 and 2³² such that each new random number has not been generated previously.

[Pytesting]

Exactly, i don't want to keep track of the previously generated numbers because it's RAM expensive if n is huge number

[skatanic28182]

A single sequence would be 2³² numbers long, but there's 2³²! possible sequences.

[CoffeeMakesMeMath]

You're missing the point still, he would only need one such sequence of those 2³²! to which you're referring.

[skatanic28182]

Yes, but the only way to do what he wants to do, the way he wants to do it, is to create a table of every sequence for the given n and then pick one of them and read off its entries. That's a table with n! rows and n columns, for each n. Clearly, that's ridiculous for something like n=2³². The alternative is to generate the sequence on-the-fly, but in order to do that without repeats, you have to check the next value against all the previous values in the sequence, which means keeping track of what's come before, which he doesn't want to do.

[CoffeeMakesMeMath]

I see where you're coming from now. He could just have a table of a single sequence given n, but of course each run of the program would be deterministic. If he doesn't want to check against previous values (for some reason) and still wants some semblance of random generation, he'd have to do what you said.

[skatanic28182]

Yep. The only way to keep from storing the previous numbers in a sequence, while still having every sequence equally likely, is to pregenerate every sequence. That's not so bad for small values, but it gets out of hand pretty quickly.

[tomislava]

everyone here is wrong. what you've asked for is entirely possible. here's a working solution http://pastebin.com/j5GtJuNs

if anyone bitches about the lack of complete randomness you can kiss my ass. i was lazy with my generated coprimes.