生成随机整数的有序列表

给定两个整数m,n，其中m<n。要求输出0~n-1范围内m个随机整数的有序列表，不允许重复。

三种方案

一、 算法依次考虑0~n-1的整数，通过适当的随机测试对每个整数进行选择。通过按序访问整数，保证输出结果有序，无重复。
该算法所需空间很少，但运行时间和n成正比,n较大不适用。

二、在初始为空的集合里插入随机整数，通过检查随机数是否在集合和排序，保证输出结果有序，无重复。
set数据结构空间开销较大，算法运行时间为O(mlogm)。

三、将包含0~n-1的数组前m个元素打乱，把前m个元素排序输出。
算法需要n个元素内存空间，O(n+mlogm)时间，时间可以降低到O(mlogm)。

源代码：

//方案一
void GetRandomOrderedList(int m, int n)
{
	time_t t;
	default_random_engine e(static_cast<unsigned>(time(&t)));
	uniform_int_distribution<int> u(0, n - 1);

	int i = 0;
	for ( ; i < n; ++i)
	{
		if ((u(e) % (n - i)) < m)
		{
			cout << i << ‘\n‘;
			--m;
		}
	}
}

//方案二
void GetRandomOrderedsets(int m, int n)
{
	time_t t;
	default_random_engine e(static_cast<unsigned>(time(&t)));
	uniform_int_distribution<int> u(0, n - 1);
	set<int> s;

	while (s.size() < m)
	{
		s.insert(u(e) % n);
	}
	set<int>::iterator i;
	for (i = s.begin(); i != s.end(); ++i)
		cout << *i << ‘\n‘;
}

//方案三
void GetRandomOrderList_DisturbElements(int m, int n)
{
	int i, j;
	vector<int> v;
	time_t t;
	default_random_engine e(static_cast<unsigned>(time(&t)));
	uniform_int_distribution<int> u(0, n - 1);


	for (i = 0; i < n; ++i)
	{
		v.push_back(i);
	}
	for (i = 0; i < m; ++i)
	{
		j = u(e);
		int t = v[i];
		v[i] = v[j];
		v[j] = t;
	}
	sort(v.begin(), v.begin()+m);
	for (i = 0; i < m; ++i)
		cout << v[i] << "\n";
}

三种方案比较：

测试的一组数据：
m = 999, n = 100000000

生成随机整数的有序列表

原文：https://www.cnblogs.com/06le/p/13757320.html