# pseudorandom function that's 1-to-1?

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

## 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 on other sites
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 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

##### 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 on other sites
Quote:
 Original post by IllcoPerhaps 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 on other sites
Quote:
 Original post by pinacoladaYeah, 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 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 on other sites
Quote:
 Original post by FlowingOozeI 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 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 on other sites
pinacolada, have you attempted the solution I gave above?

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

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5
JoeJ
14

• 14
• 10
• 23
• 9
• 32
• ### Forum Statistics

• Total Topics
632631
• Total Posts
3007534
• ### Who's Online (See full list)

There are no registered users currently online

×