c# - 确保顺序堆叠的 3 不会出现在随机排列的 4 数组中？

Question

我有一个 {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,2,3,0}，其中 0 只是放在堆栈的后面。事实上，这种情况经常发生，以至于这看起来根本不是随机的。不需要“新随机数组中 3 的原始序列”。

有没有办法改进它，以便:

1. 一个项目永远不会在原来的位置
2. 一堆 3 个连续的项目(从原始序列中永远不会 允许)(或任意数量的连续原始项目)

数组中可能有 6 个项目或 10 个项目，但我目前正在处理的只有 4 个项目。 C# 或 VB.net 都可以。

Answer 1

一堆 3 个连续项目(从不允许原始序列)

我假设 shuffle(n) 的结果用作 shuffle(n+1) 的起始序列。这很重要，因为使用相同的起始序列只会导致 {0, 1, 2, 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, 0, badNums.Length)
            BList.Add(String.Join(",", badNums))

            Array.Clear(badNums, 0, 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, 1, 2, 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),
                    String.Join(",", newItems), sw.ElapsedTicks.ToString))

    Console.WriteLine(rpt, n.ToString("0000"), String.Join(",", theseItems),
                      String.Join(",", newItems), sw.ElapsedTicks.ToString)

    ' rollover to use this result as next start
    Array.Copy(newItems, theseItems, newItems.Length)

Next

一个项目永远不会在它的原始位置这在小集合上是有意义的。但对于更大的集合，它排除了大量的合法洗牌(>60%)；在某些情况下，仅仅因为 1 件元素在同一个地方。

 Start:   {1,2,8,4,5,7,6,3,9,0}
Result:   {4,8,2,0,7,1,6,9,5,3}

由于'6'而失败，但这真的是无效的洗牌吗？三连串规则很少出现在较大的集合中 (<1%)，这可能是在浪费时间。

---

没有列表框和控制台报告(以及未显示的一些分布收集)，速度非常快。

Std Shuffle, 10k iterations, 10 elements: 12ms  (baseline)
   Modified, 10k iterations, 10 elements: 91ms
   Modified, 10k iterations, 04 elements: 48ms

修改后的洗牌依赖于重新洗牌，我知道这不会耗时。因此，当 Rule1 或 Rule2 失败时，它只是重新洗牌。 10 个元素的洗牌实际上必须执行 28k 次洗牌才能获得 10,000 个“好”的。 4 元素洗牌实际上有更高的拒绝率，因为规则更容易被如此少的项目打破(34,000 次拒绝)。

我对随机分布几乎没有兴趣，因为如果这些“改进”引入了偏差，那就不好了。 10k 4 元素分布:

seq: 3,2,1,0  count: 425
seq: 1,0,2,3  count: 406
seq: 3,2,0,1  count: 449
seq: 2,3,1,0  count: 424
seq: 0,1,3,2  count: 394
seq: 3,0,2,1  count: 371
seq: 1,2,3,0  count: 411
seq: 0,3,1,2  count: 405
seq: 2,1,3,0  count: 388
seq: 0,3,2,1  count: 375
seq: 2,0,1,3  count: 420
seq: 2,1,0,3  count: 362
seq: 3,0,1,2  count: 396
seq: 1,2,0,3  count: 379
seq: 0,1,2,3  count: 463
seq: 1,3,0,2  count: 398
seq: 2,3,0,1  count: 443
seq: 1,0,3,2  count: 451
seq: 3,1,2,0  count: 421
seq: 2,0,3,1  count: 487
seq: 0,2,3,1  count: 394
seq: 3,1,0,2  count: 480
seq: 0,2,1,3  count: 444
seq: 1,3,2,0  count: 414

与修改后的形式相比，通过较小的迭代 (1K)，您可以看到更均匀的分布。但如果您拒绝某些合法的洗牌，那是可以预料的。

十元素分布是不确定的，因为有太多的可能性(360 万次洗牌)。也就是说，经过 10k 次迭代，往往会有大约 9980 个系列，其中 12-18 个的计数为 2。