Voltar inteiro aleatório no intervalo com base no último resultado e uma semente

Question

Suponha que temos um intervalo de inteiros [a, b].Eu gostaria de ter uma função que retorna aleatório membros de dentro do intervalo, sem repetições.Uma vez que todos os membros dentro do intervalo são exploradas, a função de início para retornar o mesmo primeiro sequência aleatória novamente, na mesma ordem.

Exemplo:a=1, b=5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

Isso seria fácil de conseguir por baralhar uma matriz de todos os elementos entre a e b, e repeti-lo uma vez que a matriz está terminado.No entanto, isso tomaria muito espaço de memória, e isso não é adequado para o meu caso (eu poderia ter milhões de elementos).

Em vez disso, a função que eu gostaria de ter seria mais ou menos assim:

f(a, b, n, seed) -> n+1

Onde:

a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

O truque é saber alguma maneira de obter uma não repetidos número do intervalo baseado apenas no elemento retornado antes e a semente.No final, ele iria se comportar como uma lista circular randomizados em sua inicialização, mas sem o uso de espaço de memória.

Answer 1

Eu sugiro que você escolha uma permutação aleatória no intervalo $[a,b]$, i.é., um bijective função $\pi:[a,b]\[a,b]$.Em seguida, manter um contador $i$ que começa em $i=us$;a cada passo, a saída $\pi(i)$ e, em seguida, incremento $i$ (moldagem em torno de modo que $b+1$ torna-se $a$).

Existem métodos padronizados para a criação de uma permutação aleatória na criptografia de literatura:procurar formato de preservação de criptografia.A semente é a chave criptográfica.Você vai ser capaz de calcular $\pi(i)$ no $S(1)$ tempo e $S(1)$ o espaço, portanto, isso deve ser muito eficiente e evitar a necessidade de uma grande quantidade de armazenamento.

Se você insistir que a próxima saída deve ser uma função da saída anterior, você pode deixar $g(i)=i+1$ (exceto os que $g(b)=us$) e, em seguida, deixe $f(i)=\pi^{-1}(g(\pi(i))$, onde $\pi$ é uma permutação aleatória escolhida como acima.Isto irá, em seguida, dar-lhe um aleatório ciclo que se repete através dos elementos de $[a,b]$ em uma ordem aleatória.As saídas são a sequência $f(a),f(f(a)),f(f(f(a))),\dots$.