0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Yes, I was assuming it's a stream. I should've realized what you said earlier, it seems fairly obvious now. I had another thought, is it possible to select a permutation k elements uniformly at random from the input stream as described above? $\endgroup$ Jul 23 '20 at 1:26
  • 1
    $\begingroup$ $1\to 21\to 321\to 132 \to 4132 \to 2413 $. So it is not clear the answer must be negative to the first version $\endgroup$
    – John L.
    Jul 23 '20 at 1:30
  • $\begingroup$ @JohnL., my bad. Now I see that it's always possible. $\endgroup$
    – user114966
    Jul 23 '20 at 1:33
  • $\begingroup$ @SubhasishMukherjee It seems we can adapt Fisher–Yates shuffle simply to solve the first version. $\endgroup$
    – John L.
    Jul 23 '20 at 1:36
  • $\begingroup$ Only fixed amount of additional memory (say, three values) or not even a single value? $\endgroup$
    – greybeard
    Jul 25 '20 at 3:21
1
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ The algorithm could simpler, "for each new element 𝑘: insert 𝑘 to the end of the deque and perform a random cyclic shift of the sequence on the deque" $\endgroup$
    – John L.
    Jul 25 '20 at 15:59
  • $\begingroup$ Thanks! And also random shift in the end. Do you know a simpler reasoning to show that it works? $\endgroup$
    – user114966
    Jul 25 '20 at 20:44
  • $\begingroup$ Also (it's a bit off topic), I'm a bit confused. Essentially, my best answers, on which I spent a lot of effort, get 0 upvotes (this answer is not one of the best, but I'm still confused about it). Can you tell me please if I'm doing something wrong? $\endgroup$
    – user114966
    Jul 25 '20 at 20:47
  • 1
    $\begingroup$ No, you are not doing something wrong. Should your solution be made simpler, for example, as I mentioned, I will upvote. Note, the simpler algorithm is just repeatedly appending at the end followed by random cyclic shiting. A simple induction can prove it is correct. $\endgroup$
    – John L.
    Jul 25 '20 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.