用VBS实现Shuffle洗牌算法

昨天朋友想出一个把梭哈和象棋结合起来的玩法，游戏开始之前各自需要从象棋棋子中随机抽取五个，但是木制的棋子很容易通过纹理分辨出来，于是决定写个程序来实现随机抽取。

常规的思路是用一个数组来保存棋子，然后通过随机数来模拟抽取。但是这样抽取之后还要把这个元素从数组中删除，否则可能会重复抽取从同一个元素，然而 VBS 的数组操作非常的麻烦。

换一个思路也许会简单一点，首先把数组随机打乱（Shuffle），然后再顺序抽取前五个元素，效果和上面是一样的。就同从一副排列整齐的扑克牌中随机抽五张，与从一副洗过的扑克牌中顺序拿五张，道理是一样的。

把有序的数组随机打乱，要用到 Shuffle 算法，翻译成中文也就是洗牌算法。根据维基百科，基本的洗牌算法有两种：一种是为每张牌分配一个随机数，然后把牌按照数字的大小排序；另一种是从后往前遍历整副牌，随机交换某两张牌的位置。

第二种洗牌算法被称为 Knuth shuffle 或者 Fisher–Yates shuffle，我在这里用的就是这种洗牌算法。这种洗牌算法根据实现的不同还可以分成两种，一种是 in-place shuffle，用伪代码描述是：

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

另一种是 inside-out shuffle，用伪代码描述是：

To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based:
  a[0] ← source[0]
  for i from 1 to n − 1 do
      j ← random integer with 0 ≤ j ≤ i
      a[i] ← a[j]
      a[j] ← source[i]

in-place shuffle 比较节约内存，我在这里只给出它的 VBS 实现，读者可以尝试着自己完成 inside-out shuffle 算法的实现。

Sub Shuffle(ByRef a)
    Dim t, j, n
    n = UBound(a) : Randomize
    For i = n To 1 Step -1
        j = Int(Rnd * (i + 1))
        t = a(j) : a(j) = a(i) : a(i) = t
    Next
End Sub

'Author: Demon
'Website: https://demon.tw
'Date: 2011/12/16

a = Array("卒", "卒", "卒", "卒", "卒", "炮", "炮", "马", "马", "车", "车", "士", "士", "象", "象")

WScript.Echo Join(a)
Shuffle a
WScript.Echo Join(a)

顺便说一句，Python 标准库 Random 模块中的 Shuffle 函数使用的也是这个洗牌算法，代码在 Lib/Random.py 中：

def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """

    if random is None:
        random = self.random
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

有时间我也写一个 VBScript 标准库。恩，这只是说说而已。

参考链接：

• http://en.wikipedia.org/wiki/Shuffling
• http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

随机文章:

1. VC++7到VC6++工程的转换工具
2. 不用循环计算1到100的和
3. 用VBS实现PHP的urlencode函数
4. VBS中也有Vector
5. NDS模拟器DSEmu

这篇文章发布于 2011年12月16日，星期五，17:32，归类于 程序设计。 您可以跟踪这篇文章的评论通过 RSS 2.0 feed。 您可以留下评论，或者从您的站点trackback。