0

Lets assume an ordered finite sequence of integers A = {0,1,2, ... k}. Im looking for a (seeded) function f: A -> A where the image of f seems to be ramdom, but every element is hit exactly once (bijective).

It's importatant that someone who has access to some results of f should neither be able to estimate if he's looking at direkt neighbours f(n), f(n+1) nor should he be able to guess the next result.

One idea would be to map a range(1, k) on a shuffle(range(1, k)). But this seems very low in performance (for large k) and does miss the basic idea of a generator. The first element in the sequece should be as expensive to calculate as the n-th element.

Difference to 'normal' randomgenerators

Read carefully before marking as dublicated. I'm not looking for randomly picking from a range where collisions are possible. Also I want to calculate the n-th element without calculating all n-1elements before, like I would have to using the MT or Xorshift.

Inceddy
  • 760
  • 1
  • 6
  • 18
  • I dont think so. Randomly picking from an almost infinite amount of numbers is not bijective (there might and will be collisions). Calling `mt_rand(1,10)` ten times does not create a shuffled sequence of elements 1 to 10. – Inceddy Jul 18 '16 at 17:37
  • If your adversary has access to your results, he can always guess your last result. – Bergi Jul 18 '16 at 17:48
  • @Bergi I said access to _some_, not _all_ results. This function must not be absolute random. It should just be difficult to estimate. – Inceddy Jul 18 '16 at 17:52
  • Sounds like a possible duplicate of [Unique (non-repeating) random numbers in O(1)](http://stackoverflow.com/q/196017/1048572)? – Bergi Jul 18 '16 at 17:53
  • 1
    Read carefully: write some code and post it here. – nicomp Jul 18 '16 at 17:56
  • @Bergi Yes you are right. But the presented solutions use counter and pregenerated ranges. May be there is no solution. – Inceddy Jul 18 '16 at 17:57
  • @nicomp Code is just a tool. Don't you think I might implement a mathematical solution in any kind of language? – Inceddy Jul 18 '16 at 18:00
  • @Inceddy: There are more answer than that which pre-generates the sequence… – Bergi Jul 18 '16 at 18:02
  • http://openpatent.blogspot.de/2013/04/xincrol-unique-and-random-number.html looks good on first sight. – Inceddy Jul 18 '16 at 18:07

0 Answers0