我有一个数组{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.
