0
$\begingroup$

I'm looking for what I think is a random number generator, it should have the following properties, but I'm completely uncertain how to look for a suitable algorithm. I'd appreciate either pointers to a specific algorithm, a class of them, places for starting my research, or an explanation of why what I'm looking for isn't feasible.

Given a set of N items (item 1, item 2, … item N) I'm looking for what I presume is a pseudo random number generator that will:

  • for a given positive number input (A) return a deterministically chosen item (item B) — g(A) = B
  • where B is always between 1 and N inclusive
  • where two consecutive inputs will never return the same output — g(A) != g(A+1)
  • where g(A) is frequently not equal to g(A+N) — ie. it's not just a repeating sequence
  • any N consecutive outputs have a reasonably high probability of being the full set of 1 to N.
  • there's a broadly uniform chance of getting any B for a given A.
  • g(A) can be calculated without knowing g(A-1)

Can anyone help?

Improve this question
$\endgroup$
3
  • $\begingroup$ Are all of those requirements necessary? Here is why I ask: A true-random source would not meet those requirements. Normally a pseudorandom source is intended to mimic true randomness. If a true-random source would not meet those requirements, then that's a possible indication that the requirements might be too strong; or alternatively it might be a sign that perhaps we should not call the resulting algorithm a pseudorandom number generator. $\endgroup$
    – D.W. ♦
    Feb 15 at 6:23
  • $\begingroup$ What specifically do you mean by "any N consecutive outputs"? Do you mean that g(1), g(2), ..., g(N) have a high probability of being the full set 1,2,..,N? $\endgroup$
    – D.W. ♦
    Feb 15 at 6:25
  • $\begingroup$ Yeah; these requirements are necessary given my use case — but my use of the word "random" probably isn't! And yes, your clarification is also accurate — g(1) … g(N) has a high probability of including all of 1 … N $\endgroup$
    – JP.
    Mar 10 at 9:59

1 Answer 1

Reset to default
2
$\begingroup$

One possibility which seems to tick most of the boxes is to construct an indexed family of functions $h_i : N \rightarrow N$ with the property that for all $i$, $h_i$ is a permutation (i.e. a bijection or isomorphism). Then:

$$g(a) = h_{\left\lfloor a/N \right\rfloor}(a \bmod N)$$

This has the property that $g(Nk)$ to $g(Nk + N - 1)$ produces all of the numbers from $1$ to $N$, but the next $N$ values are a different permutation.

If $N = 2^{2b}$ for some $b$, constructing permutations is surprisingly easy by using Feistel networks, and by using operations other than exclusive or (e.g. modular arithmetic) and forgoing some symmetry, the construction can be generalised for any $N$ which isn't prime.

The one requirement that this doesn't solve is that it doesn't absolutely guarantee that $g(i+1) \ne g(i)$ if you cross a permutation boundary. But it's unlikely; you can expect it to happen roughly once in every $N^3$ values.

The only other thing I can think of is to perhaps do something clever with de Bruijn sequences, but I don't believe we know a way to pseudo-randomly index them.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I realize this is super-nitpicky, but when you write $N \to N$, do you mean $\{1,\dots,N\} \to \{1,\dots,N\}$? (And not $\mathbb{N}$, I presume?) $\endgroup$
    – D.W. ♦
    Feb 15 at 6:26
  • $\begingroup$ @D.W. Correct. I'm the kind of annoying person who uses a natural number to mean a finite set with the same cardinality. Abuse of notation. $\endgroup$
    – Pseudonym
    Feb 15 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.