rustrandom

Generate n distinct random numbers in rust

I am trying to test a program which checks for correct use of brackets. To do this I want to generate Long strings of numbers with correct use of brackets (to test incorrect uses I can easily just swap around individual characters or groups of characters)

I can easily generate a vector of non-bracket characters. However, To place brackets correctly I need n unique indices. I do not know of a way to efficiently generate random indices (a list of unique random numbers in a range) so I would like either a way to do that or a way of converting random numbers into unique indices.

The two best approaches I can think of for this are:

  1. generate a vector of all indices 0-N , shuffle it and then take the first n
  2. generate a random number, test if it is in a hashset, if isn't add it and if it is regenerate until it isn't. Repeat until the hashset has n members then convert it to a vector

The first approach is efficient for N = n + $\epsilon$ but very inefficient for N >> n while the second approach is very inefficient for N = n + $\epsilon$ but efficient for N >> n.

Note:

  1. n is the number of brackets N is the number of characters
  2. for those unfamiliar with the notation $\epsilon$ is some small positive number
Solution

  • Well you already answered your own question :^)

    I would go with No 1. While epsilon analysis is nice, in the real world, there's a lot more going on. Random accesses on vectors are very, very fast, while the hashing and regenerating random numbers is probably slow (though as always do benchmarks).

    However if you're not generating a LOT of brackets, the performance difference is probably negligible.

    For your first solution you can use the rand crate and its SliceRandom trait. Do something like:

    use rand::seq::SliceRandom;

fn whatever() {
 let mut numbers: Vec<usize> = (0..N).iter().copied().collect();
 numbers.shuffle(&mut rand::thread_rng());
 let usable_numbers = numbers[0..n];
 // Tada
}

    The other solution

    fn whatever() {
  let mut out_map = HashSet::new();
  while out_map.len() < n {
   out_map.insert(rand::thread_rng().gen::<usize>() % N);
  }

 let numbers = out_map.into_iter().collect::<Vec<_>>();

}