1
$\begingroup$

Imagine you have a number x, when x ∈ [0, N]. Is there any algorithm that can map x to y, so that y is also y ∈ [0, N] with the mapping being unique, and the distribution of all y is distributed pseudorandomly across the whole range? I know it's possible by just generating a set from 0 to N, shuffling it, and using x as an index. I want to know if there is some smarter way to do this that doesn't involve a memory footprint that is linear to x.

The Pigeonhole principle shows that this is impossible when y > x, and it is trivially possible when x = y (well... y := x), but is this possible in a manner when y is randomly distributed?

My first (bad) attempt in C# was to use a golden ratio and travel around a circle, since mathematically this is guaranteed to give a unique angle every time. In theory (phi * n) mod 360 is sort of random looking and unique. Sadly this only works if you have infinite precision and not at all when you have discrete buckets for the output, so this idea didn't really work out, even when N = 255:

Code

Result

So out of pure curiosity I'm wondering - is there some beautiful algorithm to map this so that it doesn't involve either a predefined list of candidate numbers or a list of already used numbers, or so on?

$\endgroup$
1
  • $\begingroup$ Some background: I've watched some Among Us gameplay videos on youtube, and what caught my attention is that parties work via an invite system where a unique 6-letter code is generated and players are connected by entering the same code. I started thinking how this could be implemented efficiently, and eventually I sidetracked to this generalized brain bender. $\endgroup$ Sep 28, 2020 at 0:35

0

Browse other questions tagged or ask your own question.