I had a question about random shuffling. Given a sorted list, is it possible to design an algorithm to return a uniformly random arrangement of the items in a deque with the following operations:
- read from list and add to front of deque
- read from list and add to back of deque
- remove from front of deque and add to back
- remove from back of deque and add to front
I am trying to figure out an algorithm to do this without the aid of any other arrays or memory (i.e. outside of the original list of size N and the deque, there is no additional memory). After experimenting with it, I’m doubting it’s possible to obtain a truly uniformly random arrangement of the items, but I’d love to be proven wrong. Any guidance would be appreciated.