How do I shuffle a VecDeque?

Question

I can shuffle a regular vector quite simply like this:

extern crate rand;
use rand::Rng;

fn shuffle(coll: &mut Vec<i32>) {
    rand::thread_rng().shuffle(coll);
}

The problem is, my code now requires the use of a std::collections::VecDeque instead, which causes this code to not compile.

What's the simplest way of getting around this?

Answer 1

As of Rust 1.48, VecDeque supports the make_contiguous() method. That method doesn't allocate and has complexity of O(n), like shuffling itself. Therefore you can shuffle a VecDeque by calling make_contiguous() and then shuffling the returned slice:

use rand::prelude::*;
use std::collections::VecDeque;

pub fn shuffle<T>(v: &mut VecDeque<T>, rng: &mut impl Rng) {
    v.make_contiguous().shuffle(rng);
}

Playground

Historical answer follows below.

---

Unfortunately, the rand::Rng::shuffle method is defined to shuffle slices. Due to its own complexity constraints a VecDeque cannot store its elements in a slice, so shuffle can never be directly invoked on a VecDeque.

The real requirement of the values argument to shuffle algorithm are finite sequence length, O(1) element access, and the ability to swap elements, all of which VecDeque fulfills. It would be nice if there were a trait that incorporates these, so that values could be generic on that, but there isn't one.

With the current library, you have two options:

• Use Vec::from(deque) to copy the VecDeque into a temporary Vec, shuffle the vector, and return the contents back to VecDeque. The complexity of the operation will remain O(n), but it will require a potentially large and costly heap allocation of the temporary vector.

• Implement the shuffle on VecDeque yourself. The Fisher-Yates shuffle used by rand::Rng is well understood and easy to implement. While in theory the standard library could switch to a different shuffle algorithm, that is not likely to happen in practice.

A generic form of the second option, using a trait to express the len-and-swap requirement, and taking the code of rand::Rng::shuffle, could look like this:

use std::collections::VecDeque;

// Real requirement for shuffle
trait LenAndSwap {
    fn len(&self) -> usize;
    fn swap(&mut self, i: usize, j: usize);
}

// A copy of an earlier version of rand::Rng::shuffle, with the signature
// modified to accept any type that implements LenAndSwap
fn shuffle(values: &mut impl LenAndSwap, rng: &mut impl rand::Rng) {
    let mut i = values.len();
    while i >= 2 {
        // invariant: elements with index >= i have been locked in place.
        i -= 1;
        // lock element i in place.
        values.swap(i, rng.gen_range(0..=i));
    }
}

// VecDeque trivially fulfills the LenAndSwap requirement, but
// we have to spell it out.
impl<T> LenAndSwap for VecDeque<T> {
    fn len(&self) -> usize {
        self.len()
    }
    fn swap(&mut self, i: usize, j: usize) {
        self.swap(i, j)
    }
}

fn main() {
    let mut v: VecDeque<u64> = [1, 2, 3, 4].into_iter().collect();
    shuffle(&mut v, &mut rand::thread_rng());
    println!("{:?}", v);
}