pseudorandom function that's 1-to-1?
Author
Here's what I'm trying to do. I want an algorithm that can give me a random ordering of N elements. I want it to visit each element exactly once (in other words, it's 1-to-1).
Now, this problem is easy if you make a big array that encodes the function. As in, you say "int func[N]; for (int i=0; i < N; i++) func = i;", and then you shuffle the array elements using whatever pseudorandom function you want, and now "func" gives you a random 1-to-1 translation of your N elements. Another way to solve the problem is to somewhere keep track of which elements have been visited already.
But I'd like to find a solution where you don't have to allocate memory to keep track of things. As in, both the above ideas require O(N) memory. I want a solution that uses O(1) memory. All I want is a plain old pseudorandom function, with the extra guarantee that it will spit out each number once and only once.
Any ideas?
My best attempt so far as been with modulo arithmetic. The formula "(i * p) mod N" (for i = 0..N) is guaranteed to spit out every value between 0 and N, as long as p and N are coprime. But the order it gives is not really random. With N = 20 and p = 37, I got this sequence: 0, 17, 14, 11, 8, 5, 2, 19, 16, 13, 10, 7, 4, 1, 18, 15, 12, 9, 6, 3. And it seems like no matter what value of p I pick, I get similarly linear-esque numbers.
Perhaps I'm missing the point or the following is wrong in some other way, but couldn't you just do:
Note that NUM_SHUFFLE_STEPS does not have to be equal to N. Also note that modulo is bad for rand() but it serves my example. I think you would have thought of this yourself, so I probably missed something.
Greetz,
Illco
// The numbers to be shuffledint numbers[N];// Shufflefor ( int i = 0; i < NUM_SHUFLE_STEPS; i++ ){ int a = rand() % N; int b = rand() % N; int t = numbers[a]; numbers[a] = numbers; numbers = t;}Note that NUM_SHUFFLE_STEPS does not have to be equal to N. Also note that modulo is bad for rand() but it serves my example. I think you would have thought of this yourself, so I probably missed something.
Greetz,
Illco
Your idea of using modulos with a coprime is a good one. The ordering issue becomes less a problem for certain well-chosen coprimes, but I'd suggest that you simply do multiple layers of your basic method. Given m coprimes of N named p1 .. pm (ideally, they should be relatively prime to each other, too), compute for each i0 = 0 .. N-1:
i1 = (i0 * p1) mod N
i2 = (i1 * p2) mod N
...
im = (im-1 * pm) mod N
and then your i0th index is im. The higher your m is, the more random it'll look.
This is just off the cuff, so I take no responsibility. Tell me if it works, tho.
i1 = (i0 * p1) mod N
i2 = (i1 * p2) mod N
...
im = (im-1 * pm) mod N
and then your i0th index is im. The higher your m is, the more random it'll look.
This is just off the cuff, so I take no responsibility. Tell me if it works, tho.
Author
Quote:Original post by Illco
Perhaps I'm missing the point or the following is wrong in some other way, but couldn't you just do:
....
Yeah, that would do the job. But my goal is to find a solution that does not require O(N) memory.
Quote:Original post by pinacolada
Yeah, that would do the job. But my goal is to find a solution that does not require O(N) memory.
It does not, does it? Yes for the numbers you want to permute, but no other.
I don't think it's possible. You have to somehow store the set of numbers you haven't visited yet. Since the all the possible sets have equal probabilites, you can't really compress the set in anyway.
You could maybe start with a set of numbers you've visited and halfway through switch to a set of numbers that are left. That way you'd split the memory usage. Though that wouldn't really be worth the trouble. And it's still O(N).
You could maybe start with a set of numbers you've visited and halfway through switch to a set of numbers that are left. That way you'd split the memory usage. Though that wouldn't really be worth the trouble. And it's still O(N).
Quote:Original post by FlowingOoze
I don't think it's possible. You have to somehow store the set of numbers you haven't visited yet.
Not really. The key is pseudorandomness: Given the seed and the current index, you can deterministically find the set of all values you've already visited. The trick is to be able to find an element not in that set that doesn't require exhaustively computing the set each time.
If you are willing to spend time O(n) everytime you ask for an element, it's doable. Other than that, I can't think of a good solution. It seems to me that you are trying to generate a pseudo-random permutation, and the result has length N, so there's not much you can do about it.
Quote:Original post by SneftelQuote:Original post by FlowingOoze
I don't think it's possible. You have to somehow store the set of numbers you haven't visited yet.
Not really. The key is pseudorandomness: Given the seed and the current index, you can deterministically find the set of all values you've already visited. The trick is to be able to find an element not in that set that doesn't require exhaustively computing the set each time.
Yes, I suppose that if the combinations are not equally probable, then you could represent the visited numbers in smaller space.
How about using huffman coding or arithmetic coding to store the set, if you only take a subset all of the sets. If you take logarithm of all the possible sets, then you'd need O(log(N)) to store a set.
How to pick the sets, is a problem though. You'd need to know what the sets are to encode a set.
EDIT: Oh, misread that quote. Sorry.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
