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


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.