I have a large number of people coming to my shop and want to assign ids from $1$ to at-most $n$ to all of them. While I don't know in advance how many people will arrive, I'll simply stop accepting people beyond $n$, so its going to be $n$ in the worst case.
I want to assign these in a random order (so as to minimize the information that the person can get on the ID he's going to be assigned by looking at the IDs that came before him; no more than the $O(n \log n)$ algorithm leveraging the Fisher Yates shuffle described in my first attempt below). I want to do this on the fly and without having to save the ID's I've already assigned in memory (the memory footprint should be no more than $O(\log n)$ due to the bits required to store a single ID). Is there an algorithm for this? If not, what are some good algorithms that work with $O(\log n)$ memory and do well on the objective function defined in the first edit below?
EDIT-1: To make the objective function concrete, let's say every person is given a chance to guess their ID in advance when they arrive. If they get it right, they get a 1\$ discount on any purchase. We can assume these people are all very intelligent and will maximize their odds of getting the discount. My algorithm should be such that it minimizes the average discount I end up giving them.
My attempts:
If we can work with $O(n \log n)$ memory, we would simply store the numbers $1$ to $n$ in an array and permute it randomly with the Fisher-Yates shuffle. This makes all $n!$ permutations equally likely. Then, we loop through the permuted array as customers arrive and give them their IDs. Note that unless a given customer knows my permuted array and he comes in very late, he can't get much information about the ID that's going to be assigned to him by looking at the IDs that came before him.
To do this with $O(\log n)$ memory (only the bits required for storing the IDs), one could express the numbers $1$ to $n$ in binary and permute the digits of the chronological order of any customer in some pre-specified way to get a new number. However, this doesn't make the order of the ID's a completely random permutation, since the number of 1's in binary representations of the chronological position and the assigned ID are the same. So, you could rule out certain ID's based on the chronological position. Looking at ID's assigned in the past, a customer could figure this out.
EDIT-2: With the $O(n)$ memory algorithm involving the Fisher Yates shuffle, it's hard to say what the expected discount I end up giving will be if the people don't know $n$ (see here: Expected discount shop owner will have to shell out in a guessing game with customers). But if they do know $n$, I think it'll become:
$$d = \sum\limits_{i=1}^{n}\frac{1}{i}$$
EDIT-3: @MishaLavrov pointed out that even if we assign id's per the chronological order, we need $O(\log(n))$ bits to store the ids. So, an $O(1)$ algorithm isn't possible.