Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?

The final algorithm:

for each new element k:
    perform a random cyclic shift of the sequence on the deque
    insert k to the end of the deque
    perform an inverse cyclic shift

Now, why does it work? (There is probably a simpler way to put it; this is how I understand this)

We generate a random permutation $p$ (we would need additional memory for that, but I'll explain how to avoid it). We replace each input number $a_i$ with pair $(a_i, p_i)$. Now it suffices to sort the pairs based on the second element. It works because different permutations correspond to different orders of elements after sorting.

To perform the sorting, we simply emulate insertion sort:

• Let $[p_1, ldots, p_m]$ be the current numbers in deque, and they are in sorted order.
• Then another number $k$ arrives, such that $p_1 < cdots < p_i < k < p_{i+1} < cdots < p_m$.
• We perform the cyclic shift: $[p_{i+1}, ldots, p_m, p_1, ldots, p_i]$.
• We insert $k$ in the back: $[p_{i+1}, ldots, p_m, p_1, ldots, p_i, k]$
• We perform an inverse cyclic shift: $[p_1, ldots, p_i, k, p_{i+1}, ldots, p_m]$

To avoid storing the permutation, notice that it suffices to decide the relevant order of elements at the moment of insertion. I.e. for each element, you randomly determine its position among existing elements in the deque and perform the shifts as described.