转载

生成随机排列

算法

要生成 [1..n] 的随机排列，可以使用算法 A：

生成排列 [1..n]，记为 a，其中 a[1] = 1, a[2] = 2, ..., a[n] = n。
生成 [1,n] 范围内的随机数 k，交换 a[k] 和 a[n]。
生成 [1,n-1] 范围内的随机数 k，交换 a[k] 和 a[n-1]。
...
生成 [1,3] 范围内的随机数 k，交换 a[k] 和 a[3]。
生成 [1,2] 范围内的随机数 k，交换 a[k] 和 a[2]。

注意，不能使用算法 B：

生成排列 [1..n]，记为 a，其中 a[1] = 1, a[2] = 2, ..., a[n] = n。
生成 [1,n-1] 范围内的随机数 k，交换 a[k] 和 a[n]。
生成 [1,n-2] 范围内的随机数 k，交换 a[k] 和 a[n-1]。
...
生成 [1,2] 范围内的随机数 k，交换 a[k] 和 a[3]。
生成 [1,1] 范围内的随机数 k，交换 a[k] 和 a[2]。

测试程序

根据算法 A，我们有以下 C# 程序：

using System; using System.Collections.Generic;  static class RandomPermutation {   static readonly Random rand = new Random();   static readonly byte[] seq = {1, 2, 3, 4};   static readonly int len = seq.Length;   static readonly int total = 24000000;    static void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }    static int ToValue(byte[] seq)   {     var z = 0;     foreach (var i in seq) z = z * 10 + i;     return z;   }    static int GetRandomPermutation()   {     var a = (byte[])seq.Clone();     for (var n = len; n > 1; n--)       Swap(ref a[rand.Next(n)], ref a[n - 1]);     return ToValue(a);   }    static void Main()   {     var dict = new SortedDictionary<int, int>();     for (var i = 0; i < total; i++) {       var key = GetRandomPermutation();       int count;       dict.TryGetValue(key, out count);       dict[key] = count + 1;     }     foreach (var kvp in dict)       Console.WriteLine("{0}: {1,7}", kvp.Key, kvp.Value);   } }

这个程序的 GetRandomPermutation() 方法实现了算法 A，其余的是测试代码。