我有一个数组{0,1,2,3},并且要洗牌.
This工作不错
- Public Function ShuffleArray(ByVal items() As Integer) As Integer()
- Dim ptr As Integer
- Dim alt As Integer
- Dim tmp As Integer
- Dim rnd As New Random()
- ptr = items.Length
- Do While ptr > 1
- ptr -= 1
- alt = rnd.Next(ptr - 1)
- tmp = items(alt)
- items(alt) = items(ptr)
- items(ptr) = tmp
- Loop
- Return items
- End Function
一些时间.但是,我发现它经常会生成一堆{1,3,0},其中0位于堆栈的背面.事实上,通常来说,这根本看起来不是随机的. “新的随机数组中的原始序列3”是不希望的.
有没有改善这样做：
>一个物品永远不会处于原始位置
> 3个顺序项目的堆栈(从原始序列是从不
允许)(或任何数量的顺序原始项目)
它可以是数组中的6个项目或10个项目,但是我目前正在使用的只是4个项目. C#或VB.net很好.
解决方法
一堆3个顺序项目(从原始序列是不允许的)
我假设随机播放(n)的结果是用作shuffle(n 1)的起始序列.这是不重要的,因为使用相同的起始序列只会导致{0,3}的7个有效组合.当应用程序启动时使用固定的启动顺序意味着第一次洗牌只能是那些7(可能变得足够)之一.
一个加扰类：
- Public Class Scrambler
- Private rand As Random
- Public Sub New()
- rand = New Random
- End Sub
- ' FY In-Place integer array shuffle
- Public Sub Shuffle(items() As Integer)
- Dim tmp As Integer
- Dim j As Integer
- ' hi to low,so the rand result is meaningful
- For i As Integer = items.Length - 1 To 0 Step -1
- j = rand.Next(0,i + 1) ' NB max param is EXCLUSIVE
- tmp = items(j)
- ' swap j and i
- items(j) = items(i)
- items(i) = tmp
- Next
- End Sub
- ' build a list of bad sequences
- ' fullfils the "stack of 3 sequential items (from the original sequence..." requirement
- ' nsize - allows for the "(or any number ..." portion though scanning for
- ' a series-of-5 may be fruitless
- Public Function GetBadList(source As Integer(),nSize As Integer) As List(Of String)
- Dim BList As New List(Of String)
- Dim badNums(nSize - 1) As Integer
- For n As Integer = 0 To source.Length - nSize
- Array.Copy(source,n,badNums,badNums.Length)
- BList.Add(String.Join(",",badNums))
- Array.Clear(badNums,badNums.Length)
- Next
- Return BList
- End Function
- Public Function ScrambleArray(items() As Integer,badSize As Integer) As Integer()
- ' FY is an inplace shuffler,make a copy
- Dim newItems(items.Length - 1) As Integer
- Array.Copy(items,newItems,items.Length)
- ' flags
- Dim OrderOk As Boolean = True
- Dim AllDiffPositions As Boolean = True
- Dim BadList As List(Of String) = GetBadList(items,badSize)
- ' build the bad list
- Do
- Shuffle(newItems)
- ' check if they all moved
- AllDiffPositions = True
- For n As Integer = 0 To items.Length - 1
- If newItems(n) = items(n) Then
- AllDiffPositions = False
- Exit For
- End If
- Next
- ' check for forbidden sequences
- If AllDiffPositions Then
- Dim thisVersion As String = String.Join(",newItems)
- OrderOk = True
- For Each s As String In BadList
- If thisVersion.Contains(s) Then
- OrderOk = False
- Exit For
- End If
- Next
- End If
- Loop Until (OrderOk) And (AllDiffPositions)
- Return newItems
- End Function
- End Class
测试代码/如何使用它：
- ' this series is only used once in the test loop
- Dim theseItems() As Integer = {0,3}
- Dim SeqMaker As New Scrambler ' allows one RNG used
- Dim newItems() As Integer
- ' reporting
- Dim rpt As String = "{0} Before: {1} After: {2} time:{3}"
- ListBox1.Items.Clear()
- For n As Integer = 0 To 1000
- sw.Restart()
- newItems = SeqMaker.ScrambleArray(theseItems,3) ' bad series size==3
- sw.Stop()
- ListBox1.Items.Add(String.Format(rpt,n.ToString("0000"),String.Join(",theseItems),newItems),sw.ElapsedTicks.ToString))
- Console.WriteLine(rpt,sw.ElapsedTicks.ToString)
- ' rollover to use this result as next start
- Array.Copy(newItems,theseItems,newItems.Length)
- Next
一个项目永远不会处于原来的位置,这对小集是有意义的.但是对于较大的集合,它排除了大量的合法洗牌(> 60％);在某些情况下只是因为1个项目在同一个地方.
- Start: {1,8,4,5,7,6,9,0}
- Result: {4,3}
这是因为’6’失败了,但它真的是无效的洗牌？三系列规则在较大的集合(<1％)中很少出现,这可能是浪费时间. 没有列表框和控制台报告(和一些分发收集未显示),它是相当快.
- Std Shuffle,10k iterations,10 elements: 12ms (baseline)
- Modified,10 elements: 91ms
- Modified,04 elements: 48ms
修改后的洗牌依赖于我所知道的改组不会耗时.所以,当Rule1 OrElse Rule2失败时,它只是重新洗牌. 10元素洗牌必须实际执行28k洗牌,以获得10,000个“好”的. 4元素洗牌实际上具有较高的拒绝率,因为规则更容易因为少数物品(34,000个拒绝)而中断.
这并没有像洗牌分配那样感兴趣,因为如果这些“改进”引入了一个偏见,那是不好的. 10k 4元素分布：
- seq: 3,0 count: 425
- seq: 1,3 count: 406
- seq: 3,1 count: 449
- seq: 2,0 count: 424
- seq: 0,2 count: 394
- seq: 3,1 count: 371
- seq: 1,0 count: 411
- seq: 0,2 count: 405
- seq: 2,0 count: 388
- seq: 0,1 count: 375
- seq: 2,3 count: 420
- seq: 2,3 count: 362
- seq: 3,2 count: 396
- seq: 1,3 count: 379
- seq: 0,3 count: 463
- seq: 1,2 count: 398
- seq: 2,1 count: 443
- seq: 1,2 count: 451
- seq: 3,0 count: 421
- seq: 2,1 count: 487
- seq: 0,1 count: 394
- seq: 3,2 count: 480
- seq: 0,3 count: 444
- seq: 1,0 count: 414
使用较小的迭代(1K),您可以看到更均匀的分布与修改的形式.但是,如果你拒绝某些合法的洗牌,那就是预料到的.
十元分布是不确定的,因为有这么多的可能性(360万次洗牌).也就是说,以10k次迭代,往往有大约9980系列,其中12-18的计数为2.
