Generate n distinct random numbers in rust

Question

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

Answer 1

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<_>>();

}

Answer 2

If you really want to generate n distinct random number, then this is a duplicate of How to choose several random numbers from an interval?.

However in your case, instead of first generating a sequence of non-bracket characters and then inserting brackets, it might be more efficient to generate the sequence in a single pass with something like this:

fn make_string (len: usize, mut n_brackets: usize) -> String {
    assert!(len >= 2*n_brackets);
    let mut result = String::with_capacity (len);
    let mut n_open = 0;
    let mut rng = rand::thread_rng();
    for i in 0..len {
        let sel = rng.gen_range (0 .. (len-i));
        if sel < n_open {
            result.push (')');
            n_open -= 1;
        } else if sel < n_open + 2*n_brackets {
            result.push ('(');
            n_open += 1;
            n_brackets -= 1;
        } else {
            result.push (rng.gen_range ('a' .. 'z'));
        }
    }
    result
}

Playground