목록 랜덤화

목록 랜덤화

C#에서 일반 목록의 순서를 랜덤화하는 가장 좋은 방법은 무엇입니까?저는 목록에 75개의 유한한 숫자 집합을 가지고 있습니다. 저는 복권 유형의 응용 프로그램을 위해 그것들을 그리기 위해 무작위 순서로 할당하고 싶습니다.

아무 것이나 섞기(I)ListFisher-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();

위의 코드는 많은 비판을 받는 시스템을 사용합니다.스왑 후보를 선택하는 임의의 방법입니다.속도는 빠르지만 무작위적이지는 않습니다.셔플에서 더 나은 난수 품질이 필요한 경우 시스템의 난수 생성기를 사용합니다.보안.다음과 같은 암호화:

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)에서 확인할 수 있습니다.

편집: 몇 년 전에 이 답을 쓴 이후로, 많은 사람들이 제 비교의 큰 바보 같은 결점을 지적하기 위해 제게 댓글을 달거나 편지를 썼습니다.물론 그들이 옳습니다.시스템에는 아무런 문제가 없습니다.원래 의도한 방식으로 사용된 경우 랜덤.위의 첫 번째 예에서는 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();

---

사람들이 댓글에서 지적했듯이, GUID는 무작위로 보장되지 않으므로, 우리는 대신 실제 난수 생성기를 사용해야 합니다.

private static Random rng = new Random();
...
var shuffledcards = cards.OrderBy(a => rng.Next()).ToList();

저는 이 간단한 알고리즘의 투박한 버전에 조금 놀랐습니다.Fisher-Yates (또는 Knuth shuffle)는 약간 까다롭지만 매우 작습니다.왜 그것이 까다롭습니까?난수 생성기가 다음과 같은지 여부에r(a,b)합니다. 여기서 " "는 " "입니다.b포함 또는 제외입니다.저는 또한 위키백과의 설명을 편집해서 사람들이 맹목적으로 가짜 코드를 따르지 않고 버그를 감지하기 어렵게 만들지 않도록 했습니다..Net의 경우,Random.Next(a,b) 한반번호환을 합니다.b추가 작업 없이 C#/에서 구현할 수 있는 방법은 다음과 같습니다. 예:

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

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

이 코드를 사용해 보십시오.

IEnumberable에 대한 확장 방법:

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

아이디어는 항목과 임의 순서를 가진 익명 개체를 가져온 다음 이 순서와 반환 값으로 항목을 다시 정렬하는 것입니다.

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

    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];
    }
}

사항인 " 택사에유니다합의항선다니▁note"에 유의하십시오.Random generator 기본 시.Random스레드 세이프 또는 암호화 기술이 요구사항에 충분히 강하지 않으므로, 작업에 구현을 주입할 수 있습니다.

으로 강력한 ▁aation에 한 구현Random구현은 이 답변에서 확인할 수 있습니다.

---

I 목록을 효율적인 방법으로 확장하는 아이디어가 있습니다.

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]];
}

이것은 원본을 수정하지 않는 것이 바람직할 때 제가 선호하는 셔플 방법입니다.이것은 Fisher-Yates "inside-out" 알고리즘의 변형으로, 임의의 열거 가능한 시퀀스(의 길이)에서 작동합니다.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;
}

은 " 알리다같음은범과할있수다구습니도현당할여하이위를은고즘▁from"에서 .0length - 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);

랜덤 이중(0과 1 사이에서만)을 생성하는 점은 정수 솔루션으로 축척하는 데 사용하는 것입니다.이 무작위 더블을 , ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜx그것은 항상 그럴 것입니다.0 <= x && x < 1직설적입니다.

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

맛있게 드세요!

만약 당신이 두 개를 사용해도 괜찮다면요.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 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);
}

단지 그것을 이용한 변형을 제안하고 싶었습니다.IComparer<T>그리고.List.Sort():

public class RandomIntComparer : IComparer<int>
{
    private readonly Random _random = new Random();
    
    public int Compare(int x, int y)
    {
        return _random.Next(-1, 2);
    }
}

용도:

list.Sort(new RandomIntComparer());

주로 사용하는 항목:

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);
}

더 많은 linq 패키지에서 Shuffle 확장 메소드를 사용할 수 있으며, IEnumerables에서 작동합니다.

install-package morelinq

using MoreLinq;
...    
var randomized = list.Shuffle();

고정된 숫자(75)가 있는 경우 75개의 요소로 배열을 만든 다음 목록을 열거하여 배열의 임의 위치로 요소를 이동할 수 있습니다.Fisher-Yates 셔플을 사용하여 목록 번호와 배열 인덱스의 매핑을 생성할 수 있습니다.

전환에 튜플을 사용하여 Fisher-Yates를 더 간결하고 표현력 있게 셔플할 수 있습니다.

private static readonly Random random = new Random();

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

List에 대한 확장 방법을 사용하고 스레드-세이프 랜덤 생성기 조합을 사용할 수 있습니다.저는 이것의 개선된 버전을 NuGet에서 GitHub에서 사용할 수 있는 소스 코드와 함께 패키지화했습니다.NuGet 버전에는 선택적인 암호화 강력 랜덤이 포함되어 있습니다.

NET 6.0 이전 버전:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Shuffle<T>(this IList<T> list)
{
    if (list == null) throw new ArgumentNullException(nameof(list));
    int n = list.Count;
    while (n > 1)
    {
        int k = ThreadSafeRandom.Instance.Next(n--);
        (list[n], list[k]) = (list[k], list[n]);
    }
}

internal class ThreadSafeRandom
{
    public static Random Instance => _local.Value;

    private static readonly Random _global = new Random();
    private static readonly ThreadLocal<Random> _local = new ThreadLocal<Random>(() =>
    {
        int seed;
        lock (_global)
        {
            seed = _global.Next();
        }
        return new Random(seed);
    });
}

.NET 6.0 이상의 경우:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Shuffle<T>(this IList<T> list)
{
    ArgumentNullException.ThrowIfNull(list);
    int n = list.Count;
    while (n > 1)
    {
        int k = Random.Shared.Next(n--);
        (list[n], list[k]) = (list[k], list[n]);
    }
}

추가 기능을 보려면 NuGet을 통해 라이브러리를 설치합니다.

내부에서 작업하는 대신 새 목록을 반환하고 보다 일반적인 답변을 수락하는 승인된 답변의 간단한 수정IEnumerable<T>다른 많은 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.

저는 온라인에서 흥미로운 해결책을 찾았습니다.

제공: https://improveandrepeat.com/2018/08/a-simple-way-to-shuffle-your-lists-in-c/

varshuffled = myList.주문 기준(x = > GUID).새 안내서().받는 사람();

다음은 반환할 요소 수를 지정할 수 있는 Fisher-Yates 셔플의 구현입니다. 따라서 원하는 수의 요소를 가져오기 전에 먼저 전체 컬렉션을 정렬할 필요가 없습니다.

요소 스와핑 시퀀스는 기본값에서 반대로 이루어지며, 첫 번째 요소에서 마지막 요소로 진행되므로 컬렉션의 하위 집합을 검색하면 전체 컬렉션을 셔핑하는 것과 동일한 (부분적인) 시퀀스가 생성됩니다.

collection.TakeRandom(5).SequenceEqual(collection.Shuffle().Take(5)); // true

이 알고리즘은 위키피디아의 피셔-예이츠 셔플의 더스텐펠트 (현대) 버전을 기반으로 합니다.

public static IList<T> TakeRandom<T>(this IEnumerable<T> collection, int count, Random random) => shuffle(collection, count, random);
public static IList<T> Shuffle<T>(this IEnumerable<T> collection, Random random) => shuffle(collection, null, random);
private static IList<T> shuffle<T>(IEnumerable<T> collection, int? take, Random random)
{
    var a = collection.ToArray();
    var n = a.Length;
    if (take <= 0 || take > n) throw new ArgumentException("Invalid number of elements to return.");
    var end = take ?? n;
    for (int i = 0; i < end; i++)
    {
        var j = random.Next(i, n);
        (a[i], a[j]) = (a[j], a[i]);
    }

    if (take.HasValue) return new ArraySegment<T>(a, 0, take.Value);
    return a;
}

구현:

public static class ListExtensions
{
    public static void Shuffle<T>(this IList<T> list, Random random)
    {
        for (var i = list.Count - 1; i > 0; i--)
        {
            int indexToSwap = random.Next(i + 1);
            (list[indexToSwap], list[i]) = (list[i], list[indexToSwap]);
        }
    }
}

예:

var random = new Random();
var array = new [] { 1, 2, 3 };
array.Shuffle(random);
foreach (var item in array) {
    Console.WriteLine(item);
}

의 시연.NET 피들

다음은 혼합된 값의 바이트 배열을 반환하는 효율적인 Shuffler입니다.그것은 결코 필요 이상으로 섞이지 않습니다.이전에 중단했던 위치에서 다시 시작할 수 있습니다.실제 구현(표시되지 않음)은 사용자가 지정한 교체 셔플러를 허용하는 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;
    }

`

당신의 질문은 목록을 무작위화하는 방법입니다.이는 다음을 의미합니다.

1. 모든 고유한 조합이 가능해야 합니다.
2. 모든 고유한 조합은 동일한 분포를 사용해야 합니다(일명 비편향).

이 질문에 대해 게시된 다수의 답변은 "무작위"에 대한 위의 두 가지 요구 사항을 충족하지 못합니다.

여기 피셔-예이츠 셔플 방법을 따르는 작고 편향되지 않은 의사 무작위 함수가 있습니다.

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

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

스레드 안전한 방법은 다음과 같습니다.

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());
    }
}

 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);

}

공용 목록 셔플리스트(목록) {레터 클래스 임시 요소; 목록 템플릿리스트 = new List(); 목록 목록 복사본 = new List(); 인트라넷;

    foreach (LetterClass item in list)
    {
        listcopy.Add(item);
    }

    while (listcopy.Count != 0)
    {
        rand = Random.Range(0, listcopy.Count);
        tempelement = listcopy[rand];
        templist.Add(listcopy[rand]);
        listcopy.Remove(tempelement);

    }

    return templist;

}

private List<GameObject> ShuffleList(List<GameObject> ActualList) {


    List<GameObject> newList = ActualList;
    List<GameObject> outList = new List<GameObject>();

    int count = newList.Count;

    while (newList.Count > 0) {

        int rando = Random.Range(0, newList.Count);

        outList.Add(newList[rando]);

        newList.RemoveAt(rando);

     

    }

    return (outList);

}

사용법 :

List<GameObject> GetShuffle = ShuffleList(ActualList);

오래된 게시물은 확실하지만, 저는 그냥 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

언급URL : https://stackoverflow.com/questions/273313/randomize-a-listt