All geek questions in one place

Python: generating a large unified permutation

I am not sure if this is even possible theoretically; but if so, I would like to know how to do this in Python.

I want to generate a large random permutation cheaply. For example, let's say that I want a permutation on range(10**9). I want the permutation to be homogeneous (i.e., I want the numbers everywhere without any apparent structure.) I want to have a function available to get the nth element in the permutation for each n, and I want to have one more function available to get the index of each number in the permutation.

And the big, final condition is the following: I want to do all this without saving all the elements of the permutation. (Which can be a huge space.) I want every element to be accessible, but I don't want to store all the elements, for example rangein Python 3.

Is it possible?

+4
source share
2 answers

I believe that a block cipher, such as AES, provides exactly this functionality.

+1
source

The only way I see this happening and partially fulfill your requirements: if the permutation is not random, but looks random, and this is really a series from which you can generate a_n if you know a_n-1.

: http://en.wikipedia.org/wiki/Linear_feedback_shift_register , , LSFR . 0 2 ** n-1 , . n .

, getIdxOf (val) getValOf (Idx), .

+1

Source: https://habr.com/ru/post/1533324/

More articles:


All Articles