Jump to content
  • Advertisement
Sign in to follow this  
pinacolada

pseudorandom function that's 1-to-1?

This topic is 4732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
Perhaps I'm missing the point or the following is wrong in some other way, but couldn't you just do:

// The numbers to be shuffled
int numbers[N];

// Shuffle
for ( 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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
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.

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!