random.h の uniform_pair がなんだか変

[kmyk]

random.h の uniform_pair は現状次のようになっています。
コメントは

1. 「閉区間 [l, r] から (必ずしも異なるとは限らない) 2要素をsortして返す」

な感じですが、実装は

2. 「2点以上含む閉区間 [l, r] から異なる2要素をsortして返す」

です。

library-checker-problems/common/random.h

Lines 79 to 90 in 800d18c

	// random choice two element from [lower, upper]
	template <class T>
	std::pair<T, T> uniform_pair(T lower, T upper) {
	assert(upper - lower + 1 >= 2);
	T a, b;
	do {
	a = uniform(lower, upper);
	b = uniform(lower, upper);
	} while (a == b);
	if (a > b) std::swap(a, b);
	return {a, b};
	}

そして実際の使われ方には (1.) を想定しているものがほぼすべてで、結果として微妙にバグってます。
たとえば point_add_range_sum の random.cpp では以下のように使われているんですが、以下の問題があります。

• N = 1 を許す制約だけど N = 1 で assert で落ちる。
• 長さ 1 の区間のクエリが生成されない。

library-checker-problems/datastructure/point_add_range_sum/gen/random.cpp

Lines 27 to 28 in 800d18c

	auto p = gen.uniform_pair(0, n - 1);
	p.second++;

ところで、どうせ仕様変更するなら、用途を考えると (3.) 「空でない半開区間 [l, r) から空でない部分区間を返す」にしたい気もします。

[yosupo06]

ありがとうございます、ああー大惨事…

空でない区間[l, r)を生成する用途がほとんどのはずなんですが、uniform / uniform_pairが並んでいて区間の開閉が違うと困惑するんじゃないかと思ってこうしています(uniformはuniform_int_distributonに合わせて閉区間にした) 現に失敗していますが

[yosupo06]

ランダムな2点を返すという設計はあまりおかしくない気がしてしました

[l, r) から空でないランダムな半開区間を選ぶ はuniform_pair(l, r)で、実はそのまま対応しています

[yosupo06]

なので、実は仕様変更するまでもなくkimiyukiさんの提案した仕様になっていて、使い方を完全に間違えていた が正しい気がしています😖