Re: Mapping output from a SEQUENCE into something non-repeating/colliding but random-looking?

On Apr 30, 2009, at 1:54 AM, Craig Ringer wrote:

> Hi
>
> This must be a fairly common requirement, but either I don't know
> how to
> ask Google about it or there's not as much out there as I would've
> expected.
>
> I'm looking for a way to map the output from a monotonically
> increasing
> sequence (not necessarily gapless - ie a normal Pg SEQUENCE) into a
> fairly random different value in the availible space with a 1:1
> input->output relationship. In other words, for the input "27" the
> output will always be the same (say 32 bit) number, and no other input
> will produce that output.
>
> Note that I'm *NOT* looking for a PRNG that takes the previous
> output as
> its input. That'd force me to use the same techniques as for a gapless
> sequence in Pg, with all the associated horror with locking and
> deadlocks, the performance issues, etc.
>
> Does anyone here know of a good algorithm to do this that doesn't just
> iterate `n' times through a PRNG with the same seed, but instead
> does a
> true non-colliding space mapping?
>
> If I find something good and there aren't any existing Pl/PgSQL
> implementations I'll post one for others' use, since I'm pretty sure
> it
> must come up a lot. You don't want your database to send out "invoice
> #1" or "customer #1" after all.
>
> (I'm also going to be looking for efficient ways to calculate
> effective
> check digits for arbitrary numbers within a certain range, too, and
> will
> post something for that, but that comes later).

XOR it with a constant. Or depending on your needs, just add a constant.
Or shuffle bits. Or some combination of those.

Cheers,
   Steve