配列を重複なく乱数で埋めるには

配列を重複なく乱数で埋める方法を考えていきます。なんで唐突にそんな話が始まったかというと
C#もしくはCで以下のプログラムを書いて欲しいです。【内容】... - Yahoo!知恵袋
に回答しようと思ったからです。C#なんて知らんし、いまどきCで書く人なんて居ないでしょ。

というわけでC++11の範囲で書いていきます。・・・はいそこ、今時C++11なんていう太古の規格で書くなとか言わない。

とりあえずint型のvectorを作っていますが、他のにするのもさして大変ではないですね。

下の3つのほかにさらに3つの方法が
C++で効率よく重複のない乱数列を生成する
で提示されており、そっちの方が速いです。

まずは結論

これ使えばいいんじゃね。

randseq.hpp

#pragma once

#include <random>
#include <vector>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <stdexcept>
#include <unordered_set>
#include <functional>
#include <limits>
#include <type_traits>

std::mt19937 create_rand_engine(){
	std::random_device rnd;
	std::vector<std::uint_least32_t> v(10);// 初期化用ベクタ
	std::generate(v.begin(), v.end(), std::ref(rnd));// ベクタの初期化
	std::seed_seq seed(v.begin(), v.end());
	return std::mt19937(seed);// 乱数エンジン
}

namespace detail {
	template<typename T> auto diff(T n1, T n2) -> typename std::make_unsigned<T>::type {
		static_assert(std::is_integral<T>::value, "T is not integral.");
		if (n1 < n2) std::swap(n1, n2);
		return static_cast<typename std::make_unsigned<T>::type>(n1 - n2);
	}
}

template<typename type> std::vector<type> make_rand_array_unique(const size_t size, type rand_min, type rand_max){
	if(rand_min > rand_max) std::swap(rand_min, rand_max);
	const auto max_min_diff = detail::diff(rand_max, rand_min) + 1;
	if(max_min_diff < size) throw std::runtime_error("Invalid argument");

	std::vector<type> tmp;
	auto engine = create_rand_engine();
	std::uniform_int_distribution<type> distribution(rand_min, rand_max);

	const size_t make_size = (static_cast<uintmax_t>(std::numeric_limits<double>::max()) < size) ? ((std::numeric_limits<size_t>::max() - size / 5) < size) ? size : size + size / 5 : static_cast<size_t>(size*1.2);
	tmp.reserve(make_size);
	while(tmp.size() < size){
		while(tmp.size() < make_size) tmp.push_back(distribution(engine));
		std::sort(tmp.begin(), tmp.end());
		auto unique_end = std::unique(tmp.begin(), tmp.end());

		if(size < static_cast<size_t>(std::distance(tmp.begin(), unique_end))){
			unique_end = std::next(tmp.begin(), size);
		}
		tmp.erase(unique_end, tmp.end());
	}

	std::shuffle(tmp.begin(), tmp.end(), engine);
	return tmp;
}

template<typename type> std::vector<type> make_rand_array_select(const size_t size, type rand_min, type rand_max) {
	if (rand_min > rand_max) std::swap(rand_min, rand_max);
	const auto max_min_diff = detail::diff(rand_max, rand_min) + 1;
	if (max_min_diff < size) throw std::runtime_error("Invalid argument");

	std::vector<type> tmp;
	tmp.reserve(max_min_diff);

	for (auto i = rand_min; i <= rand_max; ++i)tmp.push_back(i);

	auto engine = create_rand_engine();
	std::uniform_int_distribution<type> distribution(rand_min, rand_max);

	for (size_t cnt = 0; cnt < size; ++cnt) {
		size_t pos = std::uniform_int_distribution<size_t>(cnt, tmp.size() - 1)(engine);

		if (cnt != pos) std::swap(tmp[cnt], tmp[pos]);
	}
	tmp.erase(std::next(tmp.begin(), size), tmp.end());

	return tmp;
}

template<typename type> std::vector<type> make_rand_array_just_shuffle(const size_t size, type rand_min, type rand_max) {
	if (rand_min > rand_max) std::swap(rand_min, rand_max);
	const auto max_min_diff = detail::diff(rand_max, rand_min) + 1;
	if (max_min_diff != size) throw std::runtime_error("Invalid argument");

	auto engine = create_rand_engine();
	std::uniform_int_distribution<type> distribution(rand_min, rand_max);
	std::vector<type> re(size);
	auto t = rand_min;
	std::generate(re.begin(), re.end(), [&t]() { return t++; });
	std::shuffle(re.begin(), re.end(), engine);
	return re;
}

template<typename type> std::vector<type> make_rand_array(const size_t size, type rand_min, type rand_max) {
	if (rand_min > rand_max) std::swap(rand_min, rand_max);
	const auto max_min_diff = detail::diff(rand_max, rand_min) + 1;
	if (max_min_diff < size) throw std::runtime_error("Invalid argument");

	if (max_min_diff == size) return make_rand_array_just_shuffle(size, rand_min, rand_max);
	else if (static_cast<uintmax_t>(std::numeric_limits<double>::max()) < max_min_diff || size < (max_min_diff * 0.04)) {
		return make_rand_array_unique(size, rand_min, rand_max);
	}
	else {
		return make_rand_array_select(size, rand_min, rand_max);
	}
}

使い方

#include <chrono>
#include <utility>
#include <string>
#include"randseq.hpp"

template<class T>
void print_elapsed_time(const std::string& str, T start, T end){
	std::cout << str << " : "
		<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
		<< " msec."
		<< std::endl;
}
int main(){
	using clock = std::chrono::high_resolution_clock;

	try{
		for(auto val : {1, 5, 10, 16, 18, 19, 20, 100, 500}){
			constexpr size_t array_num = 10000;
			const int rand_max = val*array_num;
			const int rand_min = -val*array_num;

			std::cout << "array_num : " << array_num << " rand_max : " << rand_max << " rand_min : " << rand_min << std::endl;
			const auto t0 = clock::now();

			for(size_t cnt = 0; cnt < 100; ++cnt){
				make_rand_array(array_num, rand_min, rand_max);
			}

			print_elapsed_time("make_rand_array", t0, clock::now());
		}
	}
	catch(const std::exception& er){
		std::cerr << er.what() << std::endl;
	}

#ifdef _WIN32
	system("pause");
#endif
	return 0;
}

方法1 std::unordered_mapでインデックスを作って重複チェックする

頑張ればnoexceptにできるんでしょうが、面倒そうなので、ちゃんとcatchしてあげてください。

あ、やたら長いのはshuffleしたほうが速そうなときはshuffleするように書いているからです。ちなみにstd::random_shuffleはC++14では非推奨なのでstd::shuffleを使いましょう。大事なのは最後のelse節。

std::map/std::unordered_mapのkeyの存在確認はcountメンバー関数が便利ですね。

そういえばstd::mapって存在しないkeyをoperator[]で参照すると値がデフォルトコンストラクタで初期化された状態の要素を返してくれるんですね。便利。
std::mapの第2パラメータの初期値適切な例かどうかはわかりませ... - Yahoo!知恵袋

#include <vector>
#include <unordered_map>
#include <utility>
#include <random>
#include <cstdint>
#include <algorithm>
#include <stdexcept>
#include <functional>
std::mt19937 create_rand_engine(){
	std::random_device rnd;
    std::vector<std::uint_least32_t> v(10);// 初期化用ベクタ
    std::generate(v.begin(), v.end(), std::ref(rnd));// ベクタの初期化
    std::seed_seq seed(v.begin(), v.end());
    return std::mt19937(seed);// 乱数エンジン
}
std::unordered_map<int, size_t> make_index(const std::vector<int>& arr){
	std::unordered_map<int, size_t> re_index;
	for(const auto& i : arr) ++re_index[i];//存在しない要素に対してはデフォルトコンストラクタで初期化されるので0になるからこれでいい
	return re_index;
}
std::vector<int> make_rand_array(const size_t size, int min, int max){
	if(min > max) std::swap(min, max);
    const size_t max_min_diff = static_cast<size_t>(max - min + 1);
	if(max_min_diff < size) throw std::runtime_error("引数が異常です");

    auto engine = create_rand_engine();
    std::vector<int> re(size);
    if(max_min_diff == size){
    	auto i = min;
    	for(auto & r : re) r = i++;
		std::shuffle(re.begin(), re.end(), engine);
    }
	else if(max_min_diff + 1U == size){
    	std::uniform_int_distribution<size_t> distribution(0, size - 1);// distribution
    	const auto point = distribution(engine);
    	auto tmp = min;
		for(auto it = re.begin(); it < re.begin() + point; ++it, ++tmp) *it = tmp;
		++tmp;
		for(auto it = re.begin() + point; it < re.end(); ++it, ++tmp) *it = tmp;
		std::shuffle(re.begin(), re.end(), engine);
	}
	else{
    	std::uniform_int_distribution<int> distribution(min, max);// distribution
    	for(auto& r : re) r = distribution(engine);//乱数で埋める
    	for(auto re_index = make_index(re); re_index.size() != re.size(); re_index = make_index(re)){//重複は新たな乱数で埋める
    		for(auto& r : re) if(1 < re_index[r]){
    			r = distribution(engine);
    			--re_index[r];
    		}
    	}
	}
	return re;
}

使用例

#include <iostream>
#include <exception>
int main(){
	try{
	    const auto arr = make_rand_array(12, 100, 1);
	    for(auto i : arr) std::cout << i << ", ";
	    std::cout << std::endl;
	}
	catch(const std::exception& er){
		std::cerr << er.what() << std::endl;
	}
    return 0;
}

方法2 イテレータを使って線形探索して重複チェックする(AinoMegumi氏)

友達なので試しにネタ振りしたら書いてくれました。
重複しない乱数配列(C++14版)

ごめん、微妙に変えさせて。

#include <random>
#include <vector>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <stdexcept>
#include <functional>
std::mt19937 create_rand_engine(){
	std::random_device rnd;
    std::vector<std::uint_least32_t> v(10);// 初期化用ベクタ
    std::generate(v.begin(), v.end(), std::ref(rnd));// ベクタの初期化
    std::seed_seq seed(v.begin(), v.end());
    return std::mt19937(seed);// 乱数エンジン
}

std::vector<int> make_rand_array(const size_t size, int rand_min, int rand_max) {
    if (rand_min > rand_max) std::swap(rand_min, rand_max);
    const size_t max_min_diff = static_cast<size_t>(rand_max - rand_min + 1);
    if(max_min_diff < size) throw std::runtime_error("引数が異常です");

    std::vector<int> re(size);
    std::uniform_int_distribution<int> rand(rand_min, rand_max);
    auto mt = create_rand_engine();
    for (auto& i : re)i = rand(mt);
    bool is_all_no_conflict = false;
    do {    
        is_all_no_conflict = true;
        for (auto j = re.begin(); j != re.end(); ++j) {
            for (auto k = j + 1; k != re.end(); ++k) {
                if (*k == *j) {
                    *k = rand(mt);
                    is_all_no_conflict = false;
                }
            }
        }
    } while (!is_all_no_conflict);
    return re;
}

方法3 std::unordered_setを使う

重複しない乱数配列(Java版/コレクション活用?版)
をみてて、java.util.HashSet便利だなぁと思ってたんですが、ふとC++にそれくらいあるよな？と思ってぐぐったら
data structures - Java HashSet equiv in c++ - Stack Overflow
え？std::unordered_setってソートしないの？

C++11のunordered_setと、setとの所要時間を比較する - minus9d's diary
unrodered_setは、setと異なり、挿入した数字をソートせずに保存する。

おお、勝ち確定やん！(後述:そうでもなかった)だれだよ

配列を重複なく乱数で埋める方法はstd::set/std::unordered_setなんかも考えられるんですが、今回は使わずにやっていこうと思います。
乱数入れてshuffleするのは非効率的に思えるので。(速度計測してないorz)

なんてほざいてたの(私だ)。

#include <random>
#include <vector>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <stdexcept>
#include <unordered_set>
#include <functional>
std::mt19937 create_rand_engine(){
    std::random_device rnd;
    std::vector<std::uint_least32_t> v(10);// 初期化用ベクタ
    std::generate(v.begin(), v.end(), std::ref(rnd));// ベクタの初期化
    std::seed_seq seed(v.begin(), v.end());
    return std::mt19937(seed);// 乱数エンジン
}
std::vector<int> make_rand_array(const size_t size, int rand_min, int rand_max) {
	if (rand_min > rand_max) std::swap(rand_min, rand_max);
	const size_t max_min_diff = static_cast<size_t>(rand_max - rand_min + 1);
	if (max_min_diff < size) throw std::runtime_error("引数が異常です");

	std::unordered_set<int> tmp;
	auto engine = create_rand_engine();
	std::uniform_int_distribution<int> distribution(rand_min, rand_max);
	while (tmp.size() < size) tmp.insert(distribution(engine));
	return std::vector<int>(tmp.begin(), tmp.end());
}

速度比較

いやあ、下見ればわかるけど、ここまでイテレータつかうやつが遅いとは思わなかった。なんでだろうなぁ・・・。いくらなんでも遅すぎる気がするのでだれか教えてくだい。

項目	関数名
方法1 : std::unordered_map	make_rand_array_1
方法2 : 線形探索	make_rand_array_2
方法3 : std::unordered_set	make_rand_array_3

clang 3.7.0 on Wandbox

http://melpon.org/wandbox/permlink/hkHklM6K9GdTl2KY
clang++ prog.cc -stdlib=libc++ -Wall -Wextra -O2 -march=native -std=c++11
array_num : 100000rand_max : 1000000rand_min : -10000
make_rand_array_1 : 372 msec.
make_rand_array_2 : 17811 msec.
make_rand_array_3 : 41 msec.

gcc 5.2.0 on Wandbox

http://melpon.org/wandbox/permlink/Syzbm0YgS8EuODxb
g++ prog.cc -Wall -Wextra -O2 -march=native -std=c++11
array_num : 100000rand_max : 1000000rand_min : -10000
make_rand_array_1 : 338 msec.
make_rand_array_2 : 28659 msec.
make_rand_array_3 : 38 msec.

Visual Studio 2015 Community on myPC

これだけ自分のPC上です。CPUはIntel(R) Core(TM) i5-4200Mです。

/GS /GL /analyze- /W3 /Gy /Zc:wchar_t /Zi /Gm- /O2 /sdl /Fd"Release\vc140.pdb" /Zc:inline /fp:precise /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /errorReport:prompt /WX- /Zc:forScope /Gd /Oy- /Oi /MD /Fa"Release" /EHsc /nologo /Fo"Release" /Fp"Release\rand_array.pch"
array_num : 100000rand_max : 1000000rand_min : -10000
make_rand_array_1 : 163 msec.
make_rand_array_2 : 17249 msec.
make_rand_array_3 : 36 msec.