确保3顺序堆叠没有出现在4的混洗阵列？ [英] ensuring a sequential stack of 3 doesn't appear in a shuffled array of 4?
问题描述
我有的数组{0,1,2,3} ，并希望将它洗。 这正在pretty的好
I have an array of {0,1,2,3} and want to shuffle it. This is working pretty well
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 被刚放置在叠层的背面。实际上，往往不够，这不会出现随机的。不希望的三新的随机排列按照原来的顺序。
some of the time. However, I'm finding that it often produces a stack of {1,2,3,0} where 0 is just placed on the back of the stack. In fact, often enough that this doesn't appear random at all. An "original sequence of 3 in the new randomized array" is not desired.
反正有改善这一点，以便：
Is there anyway to improve this so that:
- 的产品从来没有在原来的位置
- 一叠3连续的项（从原来的顺序是从未 允许）（或任意数量的连续原始项目）
- An item is never in its original position
- A stack of 3 sequential items (from the original sequence is never allowed) (or any number of sequential original items)
这可能是6项或10个项目在数组中，但是我正与目前仅有4项。 C＃或VB.net都很好。
It could be 6 items or 10 items in the array, but what I'm working with currently is just 4 items. C# or VB.net are fine.
推荐答案
一叠3连续的项（从原来的顺序是绝不允许）的
我假定洗牌（n）是什么被用作用于洗牌的起始序列第（n + 1）的结果。这是不平凡，因为使用仅7有效组合相同的开始系列结果 {0，1，2，3} 。使用一个固定的启动顺序时，应用程序启动是指第一个洗牌只能是其中的一个7（可能改变就够了）。
I assume the result of shuffle(n) is what is used as the starting sequence for shuffle(n+1). This is non trivial because using the same start series results in only 7 valid combinations for {0, 1, 2, 3}. Using a fixed starting sequence when the app starts means the first shuffle can only be one of those 7 (probably varied enough).
一个扰码器类：
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
测试code /如何使用它：
Test code/How to use it:
' 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个项目是在同一个地点。
An item is never in its original position this sort of makes sense on small sets. But for larger sets, it rules out a large number of legitimate shuffles (>60%); in some cases just because 1 item is in the same spot.
Start: {1,2,8,4,5,7,6,3,9,0}
Result: {4,8,2,0,7,1,6,9,5,3}
这将失败，因为的6，但它确实是一个无效的洗牌？系列的三个规则显示了pretty的很少的大集合（小于1％），这可能是在浪费时间。
This fails because of the '6', but is it really an invalid shuffle? The series-of-three rule shows up pretty rarely in larger sets (<1%) that it might be a waste of time.
如果没有列表框和控制台报告（而不是出一些分布聚会），它是快速pretty的。
Without the listbox and console reports (and some distribution gathering not shown), it is pretty fast.
Std Shuffle, 10k iterations, 10 elements: 12ms (baseline)
Modified, 10k iterations, 10 elements: 91ms
Modified, 10k iterations, 04 elements: 48ms
的修饰的洗牌依赖于洗牌我知道不会费时。所以，当规则1 OrElse运算规则2失败，只是重新洗牌。 10元洗牌有实际执行28K慢腾腾得到一万个好的。四元素洗牌实际上具有较高的废品率，因为这些规则更容易有这么几项（34000不合格）。
The modified shuffle relies on reshuffling which I knew would not be time consuming. So, when Rule1 OrElse Rule2 fails, it just reshuffles. The 10 element shuffle has to actually perform 28k shuffles to get 10,000 'good' ones. The 4 element shuffle actually has a higher rejection rate because the rules are easier to break with so few items (34,000 rejects).
那不感兴趣的我远远不如洗牌分配，因为如果这些改进引入偏见，它是没有好处的。 10K 4元素分布：
That doesnt interest me nearly as much as the shuffle distribution, because if these "improvements" introduce a bias, it is no good. 10k 4 element distribution:
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），你可以看到一个更均匀的分布VS修改后的形式。但是，这是如果你拒绝特定的合法慢腾腾可以预期的。
With smaller iterations (1K) you can see a more even distribution vs the modified form. But that is to be expected if you are rejecting certain legit shuffles.
十大要素分配是不确定的，因为有这么多的可能性（360万洗牌）。这就是说，用10k迭代，有趋向于大约9980系列，具有2计数12-18
Ten element distribution is inconclusive because there are so many possibilities (3.6 million shuffles). That said, with 10k iterations, there tends to be about 9980 series, with 12-18 having a count of 2.
这篇关于确保3顺序堆叠没有出现在4的混洗阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
