确保顺序堆栈3不会出现在4个混洗数组中？

Question

我有一个阵列,{0,1,2,3}想要改变它.这工作得很好

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) 的起始序列。这并非易事，因为使用相同的起始序列只会产生 7 个有效组合{0, 1, 2, 3}。应用程序启动时使用固定的启动顺序意味着第一次随机播放只能是这 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 OrElse 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。