4

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?

3 Answers 3

7

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);
}
5
  • Thank you for this very long and detailed explanation! Commented Dec 18, 2016 at 14:05
  • Indeed, the shuffle argument is quite unfortunate seeing as the contiguity is unused. Commented Dec 18, 2016 at 19:04
  • @MatthieuM. Maybe shuffle shouldn't be defined on slices, but on a Shufflable trait (defined for slice by default) defined the same way as LenAndSwap above? That would be backward-compatible with the current definition. Commented Dec 18, 2016 at 19:10
  • make_contiguous already returns &mut [T], so you can just call .shuffle on that. Playground. Commented Feb 9, 2023 at 11:43
  • @FilipeRodrigues Great point, I've now further simplified the code in the answer. Commented Feb 9, 2023 at 13:13
2

You can use make_contiguous (documentation) to create a mutable slice that you can then shuffle:

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

fn main() {
    let mut deque = VecDeque::new();
    for p in 0..10 {
        deque.push_back(p);
    }
    deque.make_contiguous().shuffle(&mut rand::thread_rng());
    println!("Random deque: {:?}", deque)
}

Playground Link if you want to try it out online.

-2

Shuffle the components of the VecDeque separately, starting with VecDeque.html::as_mut_slices:

use rand::seq::SliceRandom; // 0.6.5;
use std::collections::VecDeque; 

fn shuffle(coll: &mut VecDeque<i32>) {
    let mut rng = rand::thread_rng();
    let (a, b) = coll.as_mut_slices();
    a.shuffle(&mut rng);
    b.shuffle(&mut rng);
}

As Lukas Kalbertodt points out, this solution never swaps elements between the two slices so a certain amount of randomization will not happen. Depending on your needs of randomization, this may be unnoticeable or a deal breaker.

2
  • 4
    As far as I understand this won't have the same effect, as elements are never swapped between both slices. So it's not a full shuffle and it's different from the "to Vec, shuffle, to VecDeque" solution... Commented Dec 18, 2016 at 14:46
  • 1
    @LukasKalbertodt a good point! I guess it depends on the usecase how valid such a randomization would be.
    – Shepmaster
    Commented Dec 18, 2016 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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