C++-怎么随机生成一个特定的数组

Question

题目是这样的，先给定一个int整型数组，怎么通过一个函数随机生成该数组的一个随机排列，分析时间复杂性。rand()函数一次只能生成一个数，对于元素很多的数组不适用。
比如:给定一个数组array1[5] = {2,6,9,15,5}，输出就是随机的一个排列，可以是array2[5] = {9,15,5,2,6}。

Answer 1

可以参考《STL源码分析》中的random_shuffle算法
思路：
对数组中的元素进行随机调换，事实上就是排列；
元素0，只有一种可能；
元素1，两种可能；
。。。
元素n-1，n-1中可能。

库中的代码比较复杂，主要含义如下。

 void random_shuffle(int a[], int n) {
for (int i=1; i<n; ++i)
swap(a[i], rand()%(i+1));
}

扩展阅读算法：next_permutation, prev_permutation

Answer 2

这个其实就是随机全排列的生成。
可以采用STL里面的洗牌算法：random_shuffle

Answer 3

这个功能标准库里面就有，名叫 std::random_shuffle，在 algorithm 头文件里有声明。大概用法如下：

 void function (int* array, int length)
{
std::random_shuffle (array, array+length);
}

random_shuffle的时间复杂度是O(N)。具体实现你可以看标准库的代码，不难，这里就不贴出来了。底层应该还是使用rand。

Answer 4

随机排列数组常用的方法有两种，算法导论一书中有提到，中译版59页，英文原版100页。

一个常用的方法是为数组的每个元素A[i]赋一个随机的优先级P[i],然后依据优先级对数组中的元素进行排序。

PERMUTE-BY-SORTING(A)
1 n ← length[A]
2 for i ← 1 to n
3 do P[i ] = RANDOM(1, n^3)
4 sort A, using P as sort keys
5 return A

其中的第3行选取的一个在1到n^3之间的随机数，使用范围1到n^3，是为了让P中所有的优先级尽可能唯一的，算法的复杂度为排序算法的复杂度。
2. 产生随机数列的一种更好的方法是原地(in place)排列给定的数列。以下程序在O(n)的时间内完成。

RANDOMIZE-IN-PLACE(A)
1 n ← length[A]
2 for i ← 1 to n
3 do swap A[i ] ↔ A[RANDOM(i, n)]

相关的证明和分析在算法导论一书中均有涉及。