問題

問題１　$2 ≤ N$ なる整数 $N$ が与えられます。$0 ≤ L < R < N$ なる整数の組 $(L, R)$ なる $(L, R)$ を一様ランダムに生成する方法を示せ
問題２　$1 ≤ N$ なる整数 $N$ が与えられます。$0 ≤ L ≤ R < N$ なる整数の組 $(L, R)$ なる $(L, R)$ を一様ランダムに生成する方法を示せ

問題１は要するに区間が与えられるので、その非空な部分区間を一様ランダム生成してくださいということですね。

問題２は $R$ の代わりに $R + 1$ を生成することにすることで問題１に帰着できますが、実用性の観点からこの記事ではこの２つを独立に解説します。

問題１の解法

$N = 8$ のときには $0 ≤ L < R < N$ なる整数の組 $(L, R)$ 全体の集合は、下の図の赤い部分ですね。ちなみに太線は $[0, N[ × [0, N[$ の範囲です。

これをバッターーンすると？？このように赤青の長方形になり、一様ランダム生成が容易になります。この長方形内で一様ランダム生成をして、青に入ってしまったら $(l, r) ↦ (r, l + 1)$により赤に全単射的に移せばよいわけです。

つまり、次のようなコードになります。

// let mut rng = StdRng::seed_from_u64(42); など
let mut l = rng.gen_range(0..n - 1);
let mut r = rng.gen_range(0..n);
if l >= r {
    (l, r) = (r, l + 1);
}

問題２の解法

問題１に帰着することもできますが、直接解いたほうがストレートです。

範囲はこれですね。

バッターーーーン！！！先ほどとバッタン式が違って $(l, r) ↦ (r, l - 1)$ になることにも注意です。

つまり、次のようなコードになります。

// let mut rng = StdRng::seed_from_u64(42); など
let mut l = rng.gen_range(0..n + 1);
let mut r = rng.gen_range(0..n);
if l >= r {
    (l, r) = (r, l - 1);
}