c# – 确保顺序堆栈3不会出现在4的混洗数组中？

我假设随机播放(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.