リストのランダム化＆lt; T＆gt;

StackOverflow https://stackoverflow.com/questions/273313

  •  07-07-2019
  •  | 
  •  

質問

C＃でジェネリックリストの順序をランダム化する最良の方法は何ですか？宝くじタイプのアプリケーションのためにそれらを描画するために、ランダムな順序を割り当てたいリストに75個の数字の有限セットがあります。

役に立ちましたか？

解決

に基づく拡張メソッドで（I）List をシャッフルしますFisher-Yatesシャッフル：

private static Random rng = new Random();  

public static void Shuffle<T>(this IList<T> list)  
{  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}

使用法：

List<Product> products = GetProducts();
products.Shuffle();

上記のコードは、非常に批判されているSystem.Randomメソッドを使用して、スワップ候補を選択します。それは高速ですが、あるべきほどランダムではありません。シャッフルでより良い品質のランダム性が必要な場合は、System.Security.Cryptographyの乱数ジェネレーターを次のように使用します。

using System.Security.Cryptography;
...
public static void Shuffle<T>(this IList<T> list)
{
    RNGCryptoServiceProvider provider = new RNGCryptoServiceProvider();
    int n = list.Count;
    while (n > 1)
    {
        byte[] box = new byte[1];
        do provider.GetBytes(box);
        while (!(box[0] < n * (Byte.MaxValue / n)));
        int k = (box[0] % n);
        n--;
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}

簡単な比較が利用可能このブログで（WayBack Machine）。

編集：数年前にこの回答を書いて以来、多くの人々が私にコメントしたり書いたりして、私の比較の大きな愚かな欠陥を指摘しました。もちろん正しいです。 System.Randomが意図した方法で使用されていれば、何も問題はありません。上記の最初の例では、Shuffleメソッド内でrng変数をインスタンス化します。これは、メソッドが繰り返し呼び出されるかどうかをトラブルにさらしています。以下は、SOで@westonから今日受け取った非常に有用なコメントに基づいた固定された完全な例です。

Program.cs：

using System;
using System.Collections.Generic;
using System.Threading;

namespace SimpleLottery
{
  class Program
  {
    private static void Main(string[] args)
    {
      var numbers = new List<int>(Enumerable.Range(1, 75));
      numbers.Shuffle();
      Console.WriteLine("The winning numbers are: {0}", string.Join(",  ", numbers.GetRange(0, 5)));
    }
  }

  public static class ThreadSafeRandom
  {
      [ThreadStatic] private static Random Local;

      public static Random ThisThreadsRandom
      {
          get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + Thread.CurrentThread.ManagedThreadId))); }
      }
  }

  static class MyExtensions
  {
    public static void Shuffle<T>(this IList<T> list)
    {
      int n = list.Count;
      while (n > 1)
      {
        n--;
        int k = ThreadSafeRandom.ThisThreadsRandom.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
      }
    }
  }
}

他のヒント

完全にランダムな順序でアイテムをシャッフルする必要がある場合（リスト内のアイテムを混ぜる場合のみ）、GUIDでアイテムを順序付けするこのシンプルで効果的なコードを好みます... 

var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();

ここでは、この単純なアルゴリズムのすべての不格好なバージョンに少し驚いています。 Fisher-Yates（またはKnuthシャッフル）は少し複雑ですが、非常にコンパクトです。ウィキペディアにアクセスすると、for-loopが逆になっているこのアルゴリズムのバージョンが表示され、多くの人はなぜ逆になっているのかを理解していないようです。主な理由は、このバージョンのアルゴリズムでは、自由に使用できる乱数ジェネレーター Random（n）に次の2つのプロパティがあることを前提としているためです。

  1. 単一の入力パラメーターとしてnを受け入れます。
  2. 0からnまでの数字を返します包括的。

ただし、.Net乱数ジェネレーターは＃2プロパティを満たしていません。代わりに、 Random.Next（n）は0からn-1までの数値を返します。 forループを逆に使用しようとすると、1つの追加操作を追加する Random.Next（n + 1）を呼び出す必要があります。

ただし、.Net乱数ジェネレーターには、aからb-1までを返す別の優れた関数 Random.Next（a、b）があります。これは、通常のforループを持つこのアルゴリズムの実装に実際に完全に適合します。苦労せずに、正しい、効率的でコンパクトな実装を次に示します。

public static void Shuffle<T>(this IList<T> list, Random rnd)
{
    for(var i=0; i < list.Count - 1; i++)
        list.Swap(i, rnd.Next(i, list.Count));
}

public static void Swap<T>(this IList<T> list, int i, int j)
{
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

IEnumerableの拡張メソッド：

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}

    public static List<T> Randomize<T>(List<T> list)
    {
        List<T> randomizedList = new List<T>();
        Random rnd = new Random();
        while (list.Count > 0)
        {
            int index = rnd.Next(0, list.Count); //pick a random item from the master list
            randomizedList.Add(list[index]); //place it at the end of the randomized list
            list.RemoveAt(index);
        }
        return randomizedList;
    }

編集 RemoveAt は、以前のバージョンの弱点です。このソリューションはそれを克服します。

public static IEnumerable<T> Shuffle<T>(
        this IEnumerable<T> source,
        Random generator = null)
{
    if (generator == null)
    {
        generator = new Random();
    }

    var elements = source.ToArray();
    for (var i = elements.Length - 1; i >= 0; i--)
    {
        var swapIndex = generator.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

オプションの Random generator に注意してください。 Random のベースフレームワーク実装がスレッドセーフではないか、ニーズに十分な暗号強度がない場合は、実装を操作。

スレッドセーフで暗号的に強力な Random 実装に適した実装は、この回答に記載されています。

これがアイデアです。IListを（できれば）効率的な方法で拡張します。 

public static IEnumerable<T> Shuffle<T>(this IList<T> list)
{
    var choices = Enumerable.Range(0, list.Count).ToList();
    var rng = new Random();
    for(int n = choices.Count; n > 1; n--)
    {
        int k = rng.Next(n);
        yield return list[choices[k]];
        choices.RemoveAt(k);
    }

    yield return list[choices[0]];
}

この単純な拡張メソッドを使用して、それを実現できます

public static class IEnumerableExtensions
{

    public static IEnumerable<t> Randomize<t>(this IEnumerable<t> target)
    {
        Random r = new Random();

        return target.OrderBy(x=>(r.Next()));
    }        
}

次の操作を行うことで使用できます

// use this on any collection that implements IEnumerable!
// List, Array, HashSet, Collection, etc

List<string> myList = new List<string> { "hello", "random", "world", "foo", "bar", "bat", "baz" };

foreach (string s in myList.Randomize())
{
    Console.WriteLine(s);
}

Ideaは、アイテムとランダムな順序の匿名オブジェクトを取得し、この順序でアイテムを並べ替えて値を返します：

var result = items.Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList()

固定数（75）の場合、75個の要素を持つ配列を作成し、リストを列挙して、要素を配列内のランダムな位置に移動できます。 Fisher-Yatesを使用して、配列番号へのリスト番号のマッピングを生成できます。シャッフル。

通常は次を使用します：

var list = new List<T> ();
fillList (list);
var randomizedList = new List<T> ();
var rnd = new Random ();
while (list.Count != 0)
{
    var index = rnd.Next (0, list.Count);
    randomizedList.Add (list [index]);
    list.RemoveAt (index);
}

これは、オリジナルを変更しないことが望ましい場合のシャッフルの好ましい方法です。これは Fisher＆＃8211; Yates＆quot ;裏返し＆quot;列挙可能なシーケンスで機能するアルゴリズム（ source の長さは最初から知る必要はありません）。

public static IList<T> NextList<T>(this Random r, IEnumerable<T> source)
{
  var list = new List<T>();
  foreach (var item in source)
  {
    var i = r.Next(list.Count + 1);
    if (i == list.Count)
    {
      list.Add(item);
    }
    else
    {
      var temp = list[i];
      list[i] = item;
      list.Add(temp);
    }
  }
  return list;
}

このアルゴリズムは、 0 から length-1 の範囲を割り当て、ランダムに選択されたインデックスを最後のインデックスとすべて交換することでインデックスをランダムに使い果たすことでも実装できます。インデックスは1回だけ選択されています。上記のコードは、追加の割り当てなしでまったく同じことを実現します。これはかなりきれいです。

Random クラスに関しては、汎用の数値ジェネレーターです（宝くじを実行している場合は、別の何かを使用することを検討します）。また、デフォルトでは時間ベースのシード値に依存します。この問題を少し軽減するには、 Random クラスに RNGCryptoServiceProvider をシードするか、これに似たメソッドで RNGCryptoServiceProvider を使用します（参照以下）均一に選択されたランダムなダブル浮動小数点値を生成しますが、宝くじを実行するには、ランダム性とランダム性ソースの性質を理解する必要があります。

var bytes = new byte[8];
_secureRng.GetBytes(bytes);
var v = BitConverter.ToUInt64(bytes, 0);
return (double)v / ((double)ulong.MaxValue + 1);

ランダムなdouble（0〜1のみ）を生成するポイントは、整数解にスケーリングするために使用することです。ランダムなダブル x に基づいてリストから何かを選択する必要がある場合は、常に 0＆lt; = x＆amp;＆amp;になります。 x＆lt; 1 は単純です。

return list[(int)(x * list.Count)];

お楽しみください

2つの Lists を使用してもかまわない場合は、おそらくこれが最も簡単な方法ですが、おそらく最も効率的または予測不可能な方法ではありません。

List<int> xList = new List<int>() { 1, 2, 3, 4, 5 };
List<int> deck = new List<int>();

foreach (int xInt in xList)
    deck.Insert(random.Next(0, deck.Count + 1), xInt);

 public Deck(IEnumerable<Card> initialCards) 
    {
    cards = new List<Card>(initialCards);
    public void Shuffle() 
     }
    {
        List<Card> NewCards = new List<Card>();
        while (cards.Count > 0) 
        {
            int CardToMove = random.Next(cards.Count);
            NewCards.Add(cards[CardToMove]);
            cards.RemoveAt(CardToMove);
        }
        cards = NewCards;
    }

public IEnumerable<string> GetCardNames() 

{
    string[] CardNames = new string[cards.Count];
    for (int i = 0; i < cards.Count; i++)
    CardNames[i] = cards[i].Name;
    return CardNames;
}

Deck deck1;
Deck deck2;
Random random = new Random();

public Form1() 
{

InitializeComponent();
ResetDeck(1);
ResetDeck(2);
RedrawDeck(1);
 RedrawDeck(2);

}



 private void ResetDeck(int deckNumber) 
    {
    if (deckNumber == 1) 
{
      int numberOfCards = random.Next(1, 11);
      deck1 = new Deck(new Card[] { });
      for (int i = 0; i < numberOfCards; i++)
           deck1.Add(new Card((Suits)random.Next(4),(Values)random.Next(1, 14)));
       deck1.Sort();
}


   else
    deck2 = new Deck();
 }

private void reset1_Click(object sender, EventArgs e) {
ResetDeck(1);
RedrawDeck(1);

}

private void shuffle1_Click(object sender, EventArgs e) 
{
    deck1.Shuffle();
    RedrawDeck(1);

}

private void moveToDeck1_Click(object sender, EventArgs e) 
{

    if (listBox2.SelectedIndex >= 0)
    if (deck2.Count > 0) {
    deck1.Add(deck2.Deal(listBox2.SelectedIndex));

}

    RedrawDeck(1);
    RedrawDeck(2);

}

並べ替えで行うことができ、ランダムを使用して比較が行われます

var rand = new Random();
var list = new List<T>();
list.sort((a,b)=>rand.Next(-1,2));

これは、シャッフルされた値のバイト配列を返す効率的なシャッフルです。必要以上にシャッフルすることはありません。以前に中断したところから再開できます。私の実際の実装（図には示されていません）は、ユーザーが指定した交換シャッフルを許可するMEFコンポーネントです。

    public byte[] Shuffle(byte[] array, int start, int count)
    {
        int n = array.Length - start;
        byte[] shuffled = new byte[count];
        for(int i = 0; i < count; i++, start++)
        {
            int k = UniformRandomGenerator.Next(n--) + start;
            shuffled[i] = array[k];
            array[k] = array[start];
            array[start] = shuffled[i];
        }
        return shuffled;
    }

`

これは、スレッドセーフな方法です。

public static class EnumerableExtension
{
    private static Random globalRng = new Random();

    [ThreadStatic]
    private static Random _rng;

    private static Random rng 
    {
        get
        {
            if (_rng == null)
            {
                int seed;
                lock (globalRng)
                {
                    seed = globalRng.Next();
                }
                _rng = new Random(seed);
             }
             return _rng;
         }
    }

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> items)
    {
        return items.OrderBy (i => rng.Next());
    }
}

インプレースで作業する代わりに新しいリストを返し、より一般的な IEnumerable＆lt; T＆gt; 他の多くのLinqメソッドと同様。

private static Random rng = new Random();

/// <summary>
/// Returns a new list where the elements are randomly shuffled.
/// Based on the Fisher-Yates shuffle, which has O(n) complexity.
/// </summary>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
    var source = list.ToList();
    int n = source.Count;
    var shuffled = new List<T>(n);
    shuffled.AddRange(source);
    while (n > 1) {
        n--;
        int k = rng.Next(n + 1);
        T value = shuffled[k];
        shuffled[k] = shuffled[n];
        shuffled[n] = value;
    }
    return shuffled;
}

    List<T> OriginalList = new List<T>();
    List<T> TempList = new List<T>();
    Random random = new Random();
    int length = OriginalList.Count;
    int TempIndex = 0;

    while (length > 0) {
        TempIndex = random.Next(0, length);  // get random value between 0 and original length
        TempList.Add(OriginalList[TempIndex]); // add to temp list
        OriginalList.RemoveAt(TempIndex); // remove from original list
        length = OriginalList.Count;  // get new list <T> length.
    }

    OriginalList = new List<T>();
    OriginalList = TempList; // copy all items from temp list to original list.

確かに古い投稿ですが、GUIDを使用しています。 

Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList();

GUIDは常に一意であり、結果が毎回変更されるたびに再生成されるためです。

この種の問題に対する非常に簡単なアプローチは、リスト内でランダムな要素のスワップを使用することです。

擬似コードでは、これは次のようになります。

do 
    r1 = randomPositionInList()
    r2 = randomPositionInList()
    swap elements at index r1 and index r2 
for a certain number of times
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top