算法

要生成 [1..n] 的随机排列,可以使用算法 A:
[《计算机程序设计艺术 卷2:半数值算法(第3版)》算法 3.4.2P(第 110 页)]

  • 生成排列 [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,其余的是测试代码。

要注意的是,C# 语言中,数组的下标是从 0 开始的。而前面描述算法 A 时,下标是从 1 开始的。

还有,Random.Next(n) 方法返回 [0,n-1] 范围内的随机数。

运行结果

这个程序的某次运行的结果是(冒号后面的数是该排列出现的次数):

1234: 999306
1243: 998918
1324: 1002026
1342: 999857
1423: 1001389
1432: 999892
2134: 1001955
2143: 999700
2314: 999546
2341: 999570
2413: 998781
2431: 999752
3124: 1001541
3142: 999276
3214: 1000892
3241: 1000928
3412: 1001220
3421: 998861
4123: 1000518
4132: 1000431
4213: 1000458
4231: 997699
4312: 997567
4321: 999917

如果把上述程序的 GetRandomPermutation() 方法中的 rand.Next(n) 改为 rand.Next(n-1),则该程序实现了算法 B,某次运行的结果如下所示:

2341: 4001963
2413: 4003021
3142: 3997535
3421: 3998602
4123: 4000183
4312: 3998696

可见,算法 B 生成的排列的第 k 位决不会出现 k,所以不是随机的。