CODEWITHSUNDEEP
pythonhashuuidhashcodeuid
helperFunction
helperFunction

Reputation: 121

A special function for uids

I have an unique identifier (uid) x, and given an integer j, I need a function f such that f(x, j) is another uid (in the same "domain" as x) such that f(x, j1) = f(x, j2) if and only if j1 = j2 and f(x, j) != x for any j.
A naive way to do this is to maintain x as a tuple (i1, i2, ..., ik) and define f(x, j) = (j, i1, i2, ..., ik). Is there a better, more efficient way to do this? I am specifically looking for python solutions.

Edit: I also need f(x1, j1) = f(x2, j2) if and only if x1 = x2 and j1 = j2

Upvotes: 0

Views: 47

Answers (1)

Silvio Mayolo
Silvio Mayolo

Reputation: 70257

If you can guarantee that j is never zero, then the function you're looking for is simply called exclusive-or.

def f(x, j):
    return x ^ j

Assume the type of unique identifiers x is int. The exclusive-or operator forms a group on Python integers, with 0 as the identity. Hence, as long as j != 0, we have x ^ j != x. And since exclusive-or forms a group, we can cancel off the x. Suppose x ^ j1 == x ^ j2. Then x ^ x ^ j1 = x ^ x ^ j2, and the exclusive-or of a value with itself is zero, so 0 ^ j1 = 0 ^ j2, hence j1 = j2.

You need j != 0, since zero is the identity of this operation.

Edit: In response to your further condition that f(x1, j1) = f(x2, j2) implies x1 = x2 and j1 = j2, I think you're stuck with what you already found (appending to the end of a tuple). That's a very powerful condition, and I think at that point you've basically got a free monoid. So I don't see a way to do better than simple linear concatenation.

Upvotes: 1

Related Questions