목록 무작위 화
C #에서 제네릭 목록의 순서를 무작위 화하는 가장 좋은 방법은 무엇입니까? 나는 복권 유형 응용 프로그램을 위해 그것들을 그리기 위해 무작위 순서를 할당하고 싶은 목록에 유한 한 75 개의 숫자 세트가 있습니다.
어떤 셔플 (I)List에 기초 확장 방법 피셔 - 예이츠 셔플 :
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 변수를 인스턴스화합니다.이 메서드가 반복적으로 호출 될 경우 문제가 발생합니다. 아래는 오늘 @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 shuffle)는 약간 까다 롭지 만 매우 컴팩트합니다. 위키피디아로 가면 for-loop가 역으로되어있는이 알고리즘의 버전을 볼 수 있으며 많은 사람들이 왜 그것이 역으로되어 있는지 이해하지 못하는 것 같습니다. 주요 이유는이 버전의 알고리즘이 임의의 숫자 생성기 Random(n)가 다음과 같은 두 가지 속성을 가지고 있다고 가정하기 때문입니다 .
- n을 단일 입력 매개 변수로 허용합니다.
- 0에서 n 까지의 숫자를 반환 합니다 .
그러나 .Net 난수 생성기는 # 2 속성을 충족하지 않습니다. 는 Random.Next(n)대신 N-1을 포함 0에서 수를 반환합니다. for-loop를 반대로 사용하려면 Random.Next(n+1)하나의 추가 작업을 추가 하는 호출해야 합니다.
그러나 .Net 난수 생성기에는 Random.Next(a,b)a에서 b-1까지를 반환하는 또 다른 멋진 함수 가 있습니다. 이것은 실제로 정상적인 for-loop를 가진이 알고리즘의 구현에 완벽하게 들어 맞습니다. 따라서 더 이상 고민하지 않고 정확하고 효율적이며 간결한 구현이 있습니다.
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);
}
아이디어는 항목 및 임의 순서로 익명 개체를 가져온 다음이 순서 및 반환 값에 따라 항목을 다시 정렬하는 것입니다.
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-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;
}
이 알고리즘은의 범위에 할당함으로써 구현 될 수있다 0행을 length - 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 <= x && x < 1간단합니다.
return list[(int)(x * list.Count)];
즐겨!
two를 사용해도 괜찮다면 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);
}
다음은 셔플 된 값의 바이트 배열을 반환하는 효율적인 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;
}
`
이를위한 스레드로부터 안전한 방법은 다음과 같습니다.
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());
}
}
내부 에서 작업하는 대신 새 목록을 반환하고 다른 많은 Linq 메서드가 수행하는 것처럼 더 일반적인 것을 받아들이 는 수락 된 답변 의 간단한 수정입니다 IEnumerable<T>.
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
참고 URL : https://stackoverflow.com/questions/273313/randomize-a-listt
'developer tip' 카테고리의 다른 글
| .NET String.Format () : 숫자에 대해 천 자리에 쉼표를 추가합니다. (0) | 2020.09.29 |
|---|---|
| Android Studio에 라이브러리 프로젝트를 어떻게 추가합니까? (0) | 2020.09.29 |
| AngularJS 컨트롤러에서보기에 HTML 삽입 (0) | 2020.09.29 |
| base64 문자열을 어떻게 인코딩하고 디코딩합니까? (0) | 2020.09.29 |
| 엄마가 말하지 않은 Vim의 어두운 구석은 무엇입니까? (0) | 2020.09.29 |