Is there an algorithm that, with an ordered list of characters {a1, a2, a3, ..., ak}, produces in O (n) time a new list of the same characters in a random order without bias? “Without bias” means the probability that any character s will appear at some position p in the list: 1 / k.
Suppose that you can create an integer without an offset from 1-k inclusively O (1) times. We also assume that access / mutation of the element O (1) is possible and that in O (k) time it is possible to create a new list of size k.
In particular, I would be interested in the "generative" algorithm. That is, I would be interested in an algorithm that has O (1) initial overhead, and then creates a new element for each slot in the list, taking O (1) times for each interval.
If the solution to the problem does not exist as described, I would still like to know about solutions that do not meet my limitations in one or more of the following ways (and / or other ways, if necessary):
- time complexity is worse than O (n).
- the algorithm is biased relative to the end positions of the characters.
- the algorithm is not generative.
I must add that this problem turns out to be the same as the problem of randomly sorting integers from 1-k, since we can sort the list of integers from 1-k, and then for each integer I in the new list, we can create the character ai.
source share