Say it is initialized with "size=5" then it might output:
3,5,2,1,4
Is there something like this?
It does not need much statistical resemblence to randomness. Just look kind of random to the eye. And the code should be short. A few lines of Javascript or so.
Maybe one approach might be to just loop through the sequence (1,2,3,4,5) and xor the number with some other number? Maybe with 0101010...?
I want the code to be complete and reproducible. So gimmeTheNumberAtPosition(x) will always return the same for the same x.
Also, FYShuffle is much more complex than I would like the algo to be.
Isn't the Lehmer code the thing that you want? Then you can specify your permutation with an integer and extract the individual digits from it repeatedly.
Fisher-Yates is one of the simplest
things out there IMO
Here is a neat explanation:
https://preshing.com/20121224/how-to-generate-a-sequence-of-...
If you need even better properties (eg cryptographically secure) you can also look at PCG with k-dimensional equidistribution:
The reason it works is because the subgroup order generated by the element has to be divisible in the group order. There's only 1 and p. So unless it's trivial (i.e., the element 1), it's going to be p and thus it generates the whole group in p steps.
Thus, the easiest solution is to take a step-size that is prime and different from you size (that works for any size). Given the index of the current element, the next index would be `(current_index + step) % size`.
They are quite efficient for both HW and SW implementations.
Yes, when initialized with "size=5" the numbers in the output must be precisely 1,2,3,4,5 but in random looking order.
And I don't want to store the whole sequence. I want to say gimmeTheNumberAtPosition(x) and it return just that number.
https://en.wikipedia.org/wiki/Fisher–Yates_shuffle
ETA: As you don't want to store the permutation, you might want to pick a number randomly from 1 to n!, and then generate the permutation on the fly up to the desired element, using the techniques outlined here:
https://stackoverflow.com/questions/29236556/how-can-i-calcu...
In other words, good old Fisher Yates, storing the resulting permutation, and a simple lookup is probably the way to go.
Edit: yes, here is an example (in the comments) of how biased this is: https://stackoverflow.com/a/18650169/923847
https://www.robweir.com/blog/2010/02/microsoft-random-browse...
The Fisher–Yates shuffle is the right way to shuffle an array in an unbiased way.
This is simple and fast, but is not secure at all. You can solve for a, b by solving the linear congruence. It also does not generate every permutation of `n`. For n = 5, only 20 sequences can be found out of 5! = 120.
Since the "randomness" of the permutation is not that great, I was looking for something better, but could not find anything. The closest I got was https://en.wikipedia.org/wiki/Xorshift#xoshiro_and_xoroshiro which only works for powers of two. A workaround would be to choose the next larger power of two and reject all random values which are smaller than `n`, but that introduces unpredictable latency and destroys the cool jump-ahead feature.
For example, with n = 5: Let a = 3 and b = 2. x = [0, 1, 2, 3, 4], a * x = [0, 3, 6, 9, 12], a * x + b = [2, 5, 8, 11, 14], a * x + b mod n = [2, 0, 3, 1, 4]
For size=1, all parameters are 1, and only result is 1.
For size 2, r can be 1 or 2, naming the permutations [1,2];[2,1] - and eg: rand_at(n=2,r=2,i=2) would return 2, but i=1, would return 2.
I'm not sure how I'd implement this - I suppose it might be possible to generate a predictable "walk" based on n/r/i?
But for sizes less than, say, a million i would think that a shuffled array would be easier?
r would need to be in the range 1..n!
[1]: http://pcgworkshop.com/archive/mawhorter2019anarchy.pdf [2]: https://github.com/solsword/anarchy
- xoring will only produce permutations that have period two, and every element will be part of a 2-cycle.
- if your n isn’t a power of two, it may produce numbers larger than n
The set of 2-cycles will have a lot of structure, too (for example, if your magic constant is even, all cycles will have either two even numbers or two odd numbers; if it is odd, all cycles will have an even and an odd number), but the above should already be bad enough to drop that idea.
if your n isn’t a power of two,
it may produce numbers larger
than n
The others are not such big problems as I don't need strong resemblence to real randomness.
For example, it will still alternate odd and even numbers.
Also, an adversary can derive the xor key from a single sample, and predict the entire sequence from it.
There is no adversary. The use case is not about security.
int start = getRandomInt(seed) % N;
double k = N / 1.618;
k = k % 2 == 0 ? k - 1 : k; // k and N must be coprime
int nextElement = k * start % N;
start++;