Encode and generate fixed sequence of unique numbers below N

Question

It is possible to create arbitrary sequence of numbers using part (it is possible to use all) of numbers in range from 0 to 2^n-1. Let consider sequences where all numbers unique.

For examples if n = 4, some sequences are:

4 2 5 7 11 3
15 1 6
6 5 8 2 3 10 12 13 4

Question: Is it possible to generate such sequence without the use of memory to store entire sequence?

I am thinking about some kind of function F, that makes only bit manipulations and gives the next number using the previous one. For example in sequence 7 3 5 9: F(7)=3, F(3)=5, F(5)=9.

How to build such function F if I know the sequence in advance?

Answer 1

Yes it is. Encryption is a bijection between the plaintext and the cyphertext. Each plaintext input results in a unique cyphertext output, which can then be uniquely decrypted back to the original plaintext.

For numbers it is easiest to use a block cipher such as DES (64 bit) or AES (128 bit). Other block sizes are possible if needed.

For a given sequence you will need to store the cypher key, usually as big as the block size, and the position you have reached in the plaintext input. Simply encrypt the integers 0, 1, 2, 3, ... in order. The output will be a series of non-repeating numbers within the given block size. To generate more numbers in the same sequence continue from the last number used. For a different sequence change the key and start again at 0. Each key defines a permutation of the possible blocks of the given size.

For a sequence allowing repeats use a hash function instead of a cipher, hashing 0, 1, 2, 3, ... etc. For different sequences use an XOR block as the equivalent of a key and XOR it with the input before hashing. You will need to keep track of the input position you have reached if you want to add to an existing sequence.

Answer 2

No, not in general. Although a sequence S does not need to be represented literally in memory in order for us to implement a generating function F, any function F effectively encodes the sequence S, and therefore memory is required.

(A generating function F is a function such that F(i), where i is an element of the sequence, is the next element of the sequence or, if i is the last element, is some value indicating that.)

Of course it is possible that some sequences, such as the trivial 0, 1, 2, 3, …, may be generated by small functions. However, consider some number of bits b. The number of different functions that can encoded by b bits is at most 2^b (using any encoding scheme you desire—source code, machine code, abstract mathematical representation, whatever). The number of different sequences is 2ⁿ!, so the number of different generating functions needed is 2ⁿ!.

Therefore 2^b ≥ 2ⁿ!, so b ≥ log₂(2ⁿ!). Thus, if we want to have enough memory to hold a generating function for any sequence for 2ⁿ, we need at least log₂(2ⁿ!) bits.