CODEWITHSUNDEEP
javarandompermutation
Jean Alexandre
Jean Alexandre

Reputation: 180

How to randomly generate a function that is a permutation for integers <10000

I want to allow users to use the same username, but have some extra id in the form #XXXX where X is a number (for instance, BestUserName#3421), similar to how is done on Battle.net for instance.

No two users should have the same username and #id combination.

Also, I don't want my users to be able to easily predict the extra id of other users. So, I can't just start with BestUserName#0000, then BestUserName#0001, BestUserName#0002, …).

Therefore, I want to generate, for each username, a bijection f(n) from all numbers between 0000 and 9999 to every number between 0000 and 9999. f must makes it hard to guess what f(n-1) is when you know f(n). Also, f(n) must be not be the same for all usernames.

Then the first user will be BestUserName#f(0000), the second one BestUserName#f(0001), and so on, and my users won't be able to guess each other's #id.

How can I do this in Java ?

Upvotes: 0

Views: 257

Answers (3)

sh1
sh1

Reputation: 4741

So, I happen to have done a parameter search in this area and found the following 14-bit hash function:

int h(int x) {
    x &= 0x3fff;
    x ^= x >> 8;
    x *= 0x68ab;
    x &= 0x3fff;
    x ^= x >> 8;
    x *= 0x594b;
    x &= 0x3fff;
    x ^= x >> 8;
    return x;
}

This hash follows the murmur3 mix function construction. The &= operations are to keep the arithmetic operating in the 14-bit overflow domain, but other than that each step is a bijection, and so the overall hash is a bijection.

Every multiplication is odd (making it co-prime to the modulo 2**14, which guarantees that all results are unique), and the shift-exclusive-or operations can be reversed by unwinding the operation one bit at a time.

But the above function only guarantees to map one number less than 16384 to another number less than 16384. We need to limit this to less than 10000.

If you wrap it in the following loop it'll be constrained to values less than 10000 (don't worry, the average number of iterations is provably 1.6384 so it's quite safe):

int f(int x) {
  do {
    x = h(x);
  } while (x >= 10000);
  return x;
}

Because the hash function inside the loop is bijective, only one input x can map to any given result. If that result is out of range, but x was in-range, then the next iteration of the hash must map to a new value. Even if it points to a new out-of-range value the chain must eventually be forced back in-range.

A wholly-out-of-range cycle can exist, but it would be unreachable from an in-range value, because the implication would be that one link in that cycle has two values that map to it (one from outside, one from inside), which cannot be achieved by a bijective function.

This implies that input to f() must be already in-range to be safe from an infinite loop.

Now to make it different for each username, try this:

int f(int x, int username_hash) {
  int m = (username_hash * 2 + 1) & 0x3fff;
  int c = (username_hash >> 13) & 0x3fff;
  do {
    x = (x * m + c) & 0x3fff;
    x = h(x);
  } while (x >= 10000);
  return x;
}

Again, multiplication by an odd number modulo a power of two is bijective, and addition modulo a power of two is also bijective. Throwing these two additional operations in there effectively extends the hash and perturbs its behaviour according to username_hash. And the outer loop keeps the result below 10000.

I'm not sure if you mean to limit the total number of users to 10000, or if you're going to keep separate counts for each contended username, but if you pass to f() that number (guaranteed to be less than 10000) along with some integer hash of the username to configure the operation, then you'll get a number out that's just as unique as the number you pass in.

Upvotes: 1

rossum
rossum

Reputation: 15685

You want a bijection. Encryption is a bijection, so just encrypt the numbers 0, 1, 2, 3... and as long as you use the same key there will be no repeats. Encryption ensures that there is no obvious order in which the numbers appear.

You want an unusual range, 0000..9999 so you will probably need Hasty Pudding cipher, which can handle many different ranges, yours included.

Upvotes: 2

pjs
pjs

Reputation: 19855

In your constructor, create an ArrayList initialized with the values 0000-9999, shuffle it, and initialize a counter to -1 (or 10000). Each time a user is added, increment (or decrement) the counter and use it to index the next element of the ArrayList. Alternatively, if you're adding the extra id as an attribute of users you can ditch the counter and just remove and assign the last (or first) element of the ArrayList.

If the assignment is supposed to be permanent, you'll have to store the prior assignments, shuffled ArrayList, and counter value so you can pick up where you left off last time.

Upvotes: 5

Related Questions