9

の配列が{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 で問題ありません。

4

11 に答える 11

2

Fisher-Yates shuffle を試みているようですが、呼び出しNextが正しくありません。への呼び出しNextはrnd.Next(ptr + 1). で呼び出すとptr - 1、4 つのアイテムのシーケンスに対して 2 つの順列しか生成されません。[0 1 2 3] の開始シーケンスでは、これらのシーケンスの 1 つが [1 2 3 0] です。説明については、下の表を参照してください。

ptr  ptr - 1    alt     Permutations            Remarks
---  -------    ---     ------------            -------
4                       [0 1 2 3]               Starting condition
3    2          1 or 0  [0 3 2 1] or [3 1 2 0]  First pass 
2    1          0       [2 3 0 1] or [2 1 3 0]  Second pass
1    0          0       [3 2 0 1] or [1 2 3 0]  Final pass

理由altは 0 が 2 回Random.Next(0)返されるためです0。

EDIT：rnd.Next(ptr)CoderDennisが指摘したように、代わりに を使用rnd.Next(ptr + 1)すると、数字を新しい位置に移動するのに適しているため、おそらく要件に近いでしょう。を使用rnd.Next(ptr + 1)すると、より多くの順列が得られますが、可能なループごとに、元の位置に数字を残す可能性のあるスワップを実行しない場合があります (シーケンス内の位置や他のスワップによって異なります)。

于 2014-10-23T21:39:53.013 に答える
2

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」のために失敗しますが、それは本当に無効なシャッフルですか? 一連の 3 ルールは、大規模なセット (<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 要素のシャッフルでは、10,000 個の「良い」シャッフルを取得するために実際に 28k シャッフルを実行する必要があります。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 万回のシャッフル) があるため、10 要素の分布は決定的ではありません。とはいえ、10,000 回の反復では、約 9980 のシリーズが存在する傾向があり、12 ～ 18 のカウントは 2 です。

于 2014-10-28T19:22:57.683 に答える
2

以下は、与えられた要件を満たすと思います。@CoderDennis の初期ランダム値と Random を渡すための修正を組み込みました。私の VB スキルは、C# と JavaScript で何年にもわたって損なわれてきたため、明らかな構文エラーについてはお詫び申し上げます。

「（または任意の数の連続した元のアイテム）」ではなく、3つの連続したアイテムのシーケンスのみを除外します。

Public Function ShuffleArray(ByVal items() As Integer, ByVal rnd As Random) As Integer()
    Dim original as Integer() = items.ToArray()
    Dim ptr As Integer
    Dim alt As Integer
    Dim tmp As Integer
    Dim stacksOfThree = new List(Of Integer())
    Dim isGood As Boolean = True

    ptr = items.Length

    Do While ptr > 2
        ptr -= 1
        stacksOfThree.Add(new Integer() { items(ptr - 2), items(ptr - 1), items(ptr) })
    Loop

    ptr = items.Length

    Do While ptr > 1
        ptr -= 1
        alt = rnd.Next(ptr)
        tmp = items(alt)
        While items(alt).Equals(items(ptr)) Or items(ptr).Equals(tmp)
            alt = rnd.Next(ptr)
            tmp = items(alt)
        End While
        items(alt) = items(ptr)
        items(ptr) = tmp
    Loop

    ptr = items.Length
    Do While ptr > 1
        ptr -= 1
        If items(ptr).Equals(original(ptr)) Then
            isGood = False
            Exit Do
        End If
    Loop

    If isGood Then
        ptr = items.Length
        Do While ptr > 2
            ptr -= 1
            For Each stack In stacksOfThree
                If stack(2).Equals(items(ptr)) And stack(1).Equals(items(ptr - 1)) And stack(0).Equals(items(ptr - 2)) Then
                    isGood = False
                    Exit For
                End If
            Next 
            If Not isGood Then
                Exit Do
            End If
        Loop
    End If

    If isGood Then
        Return items
    Else
        Return ShuffleArray(original, new Random())
    End If
End Function
于 2014-10-23T21:49:59.733 に答える
1

小さなセットの簡単な解決策:

public static List<int> Shuffle(List<int> ints)
{
    var random = new Random();
    var result = ints.ToList();
    var hs = new HashSet<int>(ints);
    for (int i = 0; i < ints.Count; i++)
    {
        result[i] = ints.Where((x, j) => j != i).Intersect(hs).OrderBy(x => random.Next()).First();
        hs.Remove(result[i]);
    }
    return result;
}
于 2014-10-23T21:52:28.163 に答える
1

結果が元の位置または結果のシーケンスに決してならないというルールを実装していません。とにかく、真にランダムなシーケンスは、これらのルールに準拠しません。ただし、実装に関していくつかの問題が見つかりました。ShuffleArrayテストでループを 100 回実行しました。以下のコードは、ランダムな結果を生成するのにはるかに優れているようです。呼び出しをループする前に、のインスタンスがRandom一度作成されていることを確認しShuffleArrayて、シードの問題を解消します。

また、あなたの への呼び出しNextは を通過していましたがptr - 1、これは正しくないと思います。ループの最初の繰り返しについて考えると、元のコードは次のようになります。

  1. ptr = items.Length4 に設定ptrします。
  2. ptr -= 13 に設定ptrします。
  3. を呼び出すrnd.Next(ptr - 1)と、0 から 1 の間の整数が選択されます。

更新されたコードは次のとおりです。

Public Function ShuffleArray(ByVal items() As Integer, ByVal rnd As Random) As Integer()
    Dim ptr As Integer
    Dim alt As Integer
    Dim tmp As Integer

    ptr = items.Length

    Do While ptr > 1
        ptr -= 1
        alt = rnd.Next(ptr)
        tmp = items(alt)
        items(alt) = items(ptr)
        items(ptr) = tmp
    Loop
    Return items
End Function

Forそして、代わりに を使用したさらに単純なバージョンを次に示しWhileます。

Public Function ShuffleArray(ByVal items() As Integer, ByVal rnd As Random) As Integer()
    Dim alt As Integer
    Dim tmp As Integer

    For ptr = items.Length - 1 To 0 Step -1
        alt = rnd.Next(ptr)
        tmp = items(alt)
        items(alt) = items(ptr)
        items(ptr) = tmp
    Next
    Return items
End Function
于 2014-10-23T20:52:39.750 に答える
1

あなたのような基準を設定すると、シャッフルはランダムな特性を失います。そして、これはテストプログラムを使用したKnuthシャッフルアルゴリズムの実装です。私が行っている 2 つの主な考えは、Random がグローバル変数であることを確認し、i がループのインデックスであり、N が配列のサイズであることを認識して、i と N から要素を選択することです。

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
  private static void Main(String[] args)
  {
    var array = new int[] { 1, 2, 3, 4 };
    Dictionary<string, int> results = new Dictionary<string, int>();
    for (int i = 0; i < 500000; i++)
    {
      var a = array.ToArray();
      Shuffller.Shuffle(a);
      var data = string.Join(" ", a);
      if (results.ContainsKey(data))
      {
        results[data]++;
      }
      else
      {
        results.Add(data, 1);
      }
    }

    foreach (var item in results.OrderBy(e => e.Key))
    {
      Console.WriteLine("{0}  => {1}", item.Key, item.Value);
    }
    Console.ReadKey();
  }

  public class Shuffller
  {
    private static Random random = new Random();
    /// <summary>
    /// * Rearranges an array of objects in uniformly random order
    ///  (under the assumption that Random generates independent
    ///  and uniformly distributed numbers).          
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="a">the array to be shuffled     </param>
    public static void Shuffle<T>(T[] a)
    {
      int N = a.Length;
      for (int i = 0; i < N; i++)
      {
        // choose index uniformly in [i, N-1]        
        int r = i + random.Next(0, N - i);
        T swap = a[r];
        a[r] = a[i];
        a[i] = swap;
      }
    }


  }  
  }

一部の結果を要素化したい場合は、2 つの配列間に類似性アルゴリズムを実装してから、しきい値を定義してみませんか。シャッフルされた配列と元の配列との間の類似性がしきい値を超えている場合は、再シャッフルします。特にランダムシャッフルが必要な場合、アルゴリズムがランダムシャッフルに基づいている場合、多くの欠陥があります。

于 2014-10-28T14:20:10.453 に答える
1

あなたはこのようなことを考えましたか？これにより、2 より長い整数の連続した文字列は表示されません。これにより、アイテムが元の位置に配置されることもありません。

注** 同一の要素を作成する場合 (配列内の 2 つの異なる場所に 9 を表示するなど)、9a を 9b のスロットにシャッフルすることができます。これは、シャッフル関数が の値を考慮しないためです。シャッフルとは、配列インデックスによってのみシャッフルすることです。

Option Strict On
Option Explicit On
Option Infer Off
Public Class Form1
    Dim rnd As New Random(Today.Millisecond)
    Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
        Dim originalArray As Integer() = {0, 1, 2, 3, 4, 5, 6, 7, 9}
        Dim sb As New System.Text.StringBuilder
        Dim final As New System.Text.StringBuilder
        Dim msg As String = "Original: {0} Shuffled: {1}"
        Dim msg2 As String = "Original: {0} Shuffled: {1} ◄- Same"
        For i2 As Integer = 1 To 3
            Dim shuffledArray As Integer() = ShuffleArray(originalArray)
            For i As Integer = 0 To shuffledArray.Count - 1
                If originalArray(i) = shuffledArray(i) Then
                    sb.AppendLine(String.Format(msg2, originalArray(i), shuffledArray(i)))
                Else
                    sb.AppendLine(String.Format(msg, originalArray(i), shuffledArray(i)))
                End If
            Next
            Dim result As String = sb.ToString.Substring(0, sb.ToString.Length - 1) & vbCrLf & vbCrLf
            final.AppendLine(result)
            sb.Clear()
        Next
        RichTextBox1.Text = final.ToString
    End Sub
    Public Function ShuffleArray(Of t)(ByVal items() As t) As t()
        Dim results As New List(Of t)
        Dim usedIndexes As New List(Of Integer)
        Do
            Dim nextIndex As Integer = rnd.Next(0, items.Count)
            If usedIndexes.IndexOf(nextIndex) = -1 Then
                If usedIndexes.Count = nextIndex Then
                    If usedIndexes.Count = items.Count - 1 Then
                        usedIndexes.Clear()
                        results.Clear()
                    End If
                    Continue Do
                End If
                If Not last3sequential(usedIndexes, nextIndex) Then
                    usedIndexes.Add(nextIndex)
                    results.Add(items(nextIndex))
                Else
                    If usedIndexes.Count > items.Count - 3 Then
                        usedIndexes.Clear()
                        results.Clear()
                    End If
                End If
            End If
        Loop Until results.Count = items.Count
        Return results.ToArray
    End Function
    Function last3sequential(usedIndexes As List(Of Integer), nextIndex As Integer) As Boolean
        If usedIndexes.Count < 2 Then Return False
        Dim last As Integer = nextIndex
        Dim secondToLast As Integer = usedIndexes(usedIndexes.Count - 1)
        Dim thirdToLast As Integer = usedIndexes(usedIndexes.Count - 2)
        If last - secondToLast = 1 AndAlso secondToLast - thirdToLast = 1 Then
            Return True
        End If
        Return False
    End Function
End Class

5 test cases:
Original: 0 Shuffled: 7
Original: 1 Shuffled: 8
Original: 2 Shuffled: 5
Original: 3 Shuffled: 2
Original: 4 Shuffled: 9
Original: 5 Shuffled: 4
Original: 6 Shuffled: 0
Original: 7 Shuffled: 6
Original: 8 Shuffled: 3
Original: 9 Shuffled: 1 

Original: 0 Shuffled: 4
Original: 1 Shuffled: 2
Original: 2 Shuffled: 9
Original: 3 Shuffled: 6
Original: 4 Shuffled: 7
Original: 5 Shuffled: 0
Original: 6 Shuffled: 3
Original: 7 Shuffled: 5
Original: 8 Shuffled: 1
Original: 9 Shuffled: 8 

Original: 0 Shuffled: 8
Original: 1 Shuffled: 7
Original: 2 Shuffled: 6
Original: 3 Shuffled: 2
Original: 4 Shuffled: 0
Original: 5 Shuffled: 1
Original: 6 Shuffled: 9
Original: 7 Shuffled: 4
Original: 8 Shuffled: 5
Original: 9 Shuffled: 3 

Original: 0 Shuffled: 6
Original: 1 Shuffled: 4
Original: 2 Shuffled: 8
Original: 3 Shuffled: 7
Original: 4 Shuffled: 9
Original: 5 Shuffled: 2
Original: 6 Shuffled: 5
Original: 7 Shuffled: 3
Original: 8 Shuffled: 1
Original: 9 Shuffled: 0 

Original: 0 Shuffled: 6
Original: 1 Shuffled: 9
Original: 2 Shuffled: 0
Original: 3 Shuffled: 1
Original: 4 Shuffled: 5
Original: 5 Shuffled: 2
Original: 6 Shuffled: 3
Original: 7 Shuffled: 8
Original: 8 Shuffled: 7
Original: 9 Shuffled: 4
于 2014-10-28T04:51:28.810 に答える
-1

あなたが見ているのは、 Random クラスに値をシードしていないためだと思います。int をシード値として受け入れるコンストラクターを試すことをお勧めします。単純なシード値は、ティックの数になりますDateTime.Now.Ticks

Random クラスの詳細については、次のリンクを参照してください: http://msdn.microsoft.com/en-us/library/system.random.aspx

于 2013-10-04T20:15:24.193 に答える