用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 ≤ ji
       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 ≤ ji
      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: http://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 标准库。恩,这只是说说而已。

参考链接:

随机文章:

  1. 用VBS修改Windows用户密码
  2. 用VBS实现Bencode算法
  3. C语言标准库函数rand与多线程
  4. TiddlyWiki
  5. VBS获取GZIP压缩的HTTP内容

一条评论 发表在“用VBS实现Shuffle洗牌算法”上

  1. yu2n说道:

    ‘VBS Function
    Sub Shuffle_inside_out(ByRef a)
    Dim source, t, j, n
    source = a
    n = UBound(a) : Randomize
    For i = 1 To n Step 1
    j = Int(Rnd * (i + 1))
    a(i) = a(j) : a(j) = source(i)
    Next
    End Sub

留下回复