.NET을 사용하여 배열을 무작위로 만드는 가장 좋은 방법

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

문제

.NET을 사용하여 문자열 배열을 무작위로 만드는 가장 좋은 방법은 무엇입니까?내 배열에는 약 500개의 문자열이 포함되어 있으며 새 배열을 만들고 싶습니다. Array 동일한 문자열이지만 순서는 무작위입니다.

답변에 C# 예제를 포함해 주세요.

도움이 되었습니까?

해결책

.NET 3.5를 사용하는 경우 다음 IEnumerable 기능을 사용할 수 있습니다(C#이 아닌 VB.NET이지만 아이디어는 명확해야 합니다...).

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();

편집하다:좋습니다. 해당 VB.NET 코드는 다음과 같습니다.

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()

두 번째 편집은 System.Random이 시간 기반 시퀀스 반환으로 인해 "스레드 안전하지 않고" "장난감 앱에만 적합"하다는 설명에 대한 응답입니다.내 예제에서 사용된 것처럼 Random()은 배열을 무작위로 다시 입력하는 루틴을 허용하지 않는 한 완벽하게 스레드로부터 안전합니다. 이 경우 다음과 같은 것이 필요합니다. lock (MyRandomArray) 어쨌든 귀하의 데이터가 손상되지 않도록 보호하기 위해 rnd 또한.

또한 엔트로피 소스로서 System.Random이 그다지 강력하지 않다는 점도 잘 이해해야 합니다.에 언급된 바와 같이 MSDN 문서, 다음에서 파생된 것을 사용해야 합니다. System.Security.Cryptography.RandomNumberGenerator 보안과 관련된 일을 하고 있다면.예를 들어:

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

다른 팁

다음 구현에서는 피셔-예이츠 알고리즘 일명 Knuth Shuffle.O(n) 시간에 실행되고 제자리에서 섞이므로 더 많은 코드 줄이기는 하지만 '무작위 정렬' 기술보다 성능이 더 좋습니다.보다 여기 일부 비교 성능 측정을 위해.저는 System.Random을 사용했는데 이는 암호화 이외의 목적으로도 괜찮습니다.*

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

용법:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* 더 긴 배열의 경우 (매우 큰) 수의 순열을 동일하게 만들려면 각 스왑에 대해 많은 반복을 통해 의사 난수 생성기(PRNG)를 실행하여 충분한 엔트로피를 생성해야 합니다.500개 요소 배열의 경우 가능한 500개 중 아주 작은 부분에 불과합니다!PRNG를 사용하여 순열을 얻을 수 있습니다.그럼에도 불구하고 Fisher-Yates 알고리즘은 편견이 없으므로 셔플은 사용하는 RNG만큼 좋습니다.

당신은 셔플링 알고리즘을 찾고 있는 거죠, 그렇죠?

좋습니다. 이를 수행하는 방법에는 두 가지가 있습니다.영리하지만 사람들은 항상 그것을 오해하고 잘못 이해하는 것 같아서 결국 그다지 영리하지는 않을 수도 있고, 멍청한 사람들은- 하지만 그게 효과가 있기 때문에 누가 신경쓰겠어요.

멍청한 방법

  • 첫 번째 배열의 복제본을 생성하되 각 문자열에 임의의 숫자를 태그로 지정해야 합니다.
  • 난수를 기준으로 중복 배열을 정렬합니다.

이 알고리즘은 잘 작동하지만 난수 생성기가 동일한 숫자로 두 문자열에 태그를 지정하지 않도록 해야 합니다.소위 때문에 생일 역설, 이는 예상보다 자주 발생합니다.시간 복잡도는 O(N 통나무 N).

영리한 방법

나는 이것을 재귀 알고리즘으로 설명하겠습니다.

크기 배열을 섞으려면 N ([0.. 범위의 인덱스N-1]):

만약에 N = 0
  • 아무것도하지 마세요
만약에 N > 0
  • (재귀 단계) 첫 번째를 섞다 N-1 배열 요소
  • 임의의 인덱스를 선택하고, 엑스, 범위 [0..N-1]
  • 인덱스의 요소를 교환 N-1은 인덱스에 요소가 있음 엑스

반복적으로 동등한 것은 배열을 통해 반복자를 이동하면서 진행하면서 임의의 요소로 교체하는 것입니다. 그러나 요소와 교체할 수는 없습니다. ~ 후에 반복자가 가리키는 것.이는 매우 흔한 실수이며 편향된 셔플을 초래합니다.

시간 복잡도는 O(N).

이 알고리즘은 간단하지만 효율적이지 않습니다. O(N2).모든 "order by" 알고리즘은 일반적으로 O(N log N)입니다.아마도 수십만 개의 요소 아래에서는 차이가 없지만 큰 목록의 경우에는 차이가 있을 것입니다.

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

O(N인 이유2) 미묘합니다. 목록.제거() 끝부터 순서대로 제거하지 않는 한 O(N) 작업입니다.

Matt Howells에서 확장 방법을 만들 수도 있습니다.예.

   namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

그런 다음 다음과 같이 사용할 수 있습니다. 

        string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();

여러 문자열을 이동해야 하므로 배열을 무작위로 지정하는 것은 집중적입니다.왜 배열에서 무작위로 읽지 않습니까?최악의 경우에는 getNextString()을 사용하여 래퍼 클래스를 생성할 수도 있습니다.정말로 무작위 배열을 생성해야 한다면 다음과 같이 할 수 있습니다.

for i = 0 -> i= array.length * 5
   swap two strings in random places

*5는 임의적입니다.

내 머리 꼭대기에서 생각하면 다음과 같이 할 수 있습니다.

public string[] Randomize(string[] input)
{
  List<string> inputList = input.ToList();
  string[] output = new string[input.Length];
  Random randomizer = new Random();
  int i = 0;

  while (inputList.Count > 0)
  {
    int index = r.Next(inputList.Count);
    output[i++] = inputList[index];
    inputList.RemoveAt(index);
  }

  return (output);
}

동일한 길이의 임의의 부동 소수점 또는 정수 배열을 생성합니다.해당 어레이를 정렬하고 대상 어레이에서 해당 스왑을 수행하십시오.

이는 진정으로 독립적인 정렬을 생성합니다.

Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();

while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}

Jacco, 사용자 정의 IComparer 솔루션은 안전하지 않습니다.정렬 루틴이 제대로 작동하려면 비교자가 여러 요구 사항을 준수해야 합니다.그 중 첫 번째는 일관성입니다.동일한 개체 쌍에 대해 비교자가 호출되는 경우 항상 동일한 결과를 반환해야 합니다.(비교 역시 전이적이어야 합니다).

이러한 요구 사항을 충족하지 못하면 정렬 루틴에서 무한 루프 가능성을 포함하여 여러 가지 문제가 발생할 수 있습니다.

임의의 숫자 값을 각 항목과 연관시킨 다음 해당 값을 기준으로 정렬하는 솔루션과 관련하여 두 항목에 동일한 숫자 값이 할당될 때마다 출력의 무작위성이 손상되므로 출력에 고유한 편향이 발생합니다.("안정적인" 정렬 루틴에서는 입력의 첫 번째 항목이 출력의 첫 번째 항목이 됩니다.Array.Sort는 안정적이지 않지만 Quicksort 알고리즘에 의해 수행된 분할을 기반으로 한 편향은 여전히 ​​존재합니다.

어느 수준의 무작위성이 필요한지 생각해 볼 필요가 있습니다.결정적인 공격자로부터 보호하기 위해 암호화 수준의 무작위성이 필요한 포커 사이트를 운영하는 경우 노래 재생 목록을 무작위로 지정하려는 사람과는 매우 다른 요구 사항이 있습니다.

노래 목록 섞기의 경우 시드 PRNG(예: System.Random)를 사용하는 데 문제가 없습니다.포커 사이트의 경우 그것은 선택 사항도 아니며 stackoverflow에서 다른 사람이 당신을 위해 해줄 것보다 훨씬 더 열심히 문제에 대해 생각해야 합니다.(암호화 RNG를 사용하는 것은 시작일 뿐입니다. 알고리즘이 편향을 도입하지 않는지, 충분한 엔트로피 소스가 있는지, 후속 무작위성을 손상시킬 수 있는 내부 상태를 노출하지 않는지 확인해야 합니다.)

이 게시물은 이미 꽤 좋은 답변을 받았습니다. 빠르고 편견 없는 결과를 얻으려면 Fisher-Yates 셔플의 Durstenfeld 구현을 사용하세요.일부 구현이 게시되기도 했지만 일부는 실제로 올바르지 않습니다.

나는 얼마 전에 두 개의 게시물을 썼습니다. 이 기술을 사용하여 전체 및 부분 셔플 구현, 그리고 (이 두 번째 링크는 제가 가치를 더하고 싶은 곳입니다) 구현이 편향되지 않았는지 확인하는 방법에 대한 후속 게시물, 셔플 알고리즘을 확인하는 데 사용할 수 있습니다.두 번째 게시물의 끝에서 난수 선택 시 단순한 실수로 인해 발생할 수 있는 영향을 확인할 수 있습니다.

좋아, 이것은 분명히 내 입장에서 부딪힌 일이지만(죄송합니다...), 나는 종종 매우 일반적이고 암호화적으로 강력한 방법을 사용합니다.

public static class EnumerableExtensions
{
    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
    {
        var randomIntegerBuffer = new byte[4];
        Func<int> rand = () =>
                             {
                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);
                             };
        return from item in enumerable
               let rec = new {item, rnd = rand()}
               orderby rec.rnd
               select rec.item;
    }
}

Shuffle()은 모든 IEnumerable의 확장이므로 목록에서 0부터 1000까지의 숫자를 무작위 순서로 가져오는 작업을 수행할 수 있습니다.

Enumerable.Range(0,1000).Shuffle().ToList()

정렬 값은 시퀀스의 요소당 정확히 한 번씩 생성되고 기억되기 때문에 이 방법은 정렬 시에도 놀라운 일이 아닙니다.

복잡한 알고리즘은 필요하지 않습니다.

단 하나의 간단한 라인:

Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

우리는 Array 에 List 먼저, 사용하지 않으면 List 우선.

또한 이는 매우 큰 배열에는 효율적이지 않습니다.그렇지 않으면 깨끗하고 간단합니다.

이는 다음을 기반으로 하는 완벽하게 작동하는 콘솔 솔루션입니다. 여기에 제공된 예:

class Program
{
    static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };

    static void Main()
    {
        var result = Shuffle(words1);
        foreach (var i in result)
        {
            Console.Write(i + " ");
        }
        Console.ReadKey();
    }

   static string[] Shuffle(string[] wordArray) {
        Random random = new Random();
        for (int i = wordArray.Length - 1; i > 0; i--)
        {
            int swapIndex = random.Next(i + 1);
            string temp = wordArray[i];
            wordArray[i] = wordArray[swapIndex];
            wordArray[swapIndex] = temp;
        }
        return wordArray;
    }         
}

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        List<int> numList = new List<int>();
        numList.AddRange(numbers);

        Console.WriteLine("Original Order");
        for (int i = 0; i < numList.Count; i++)
        {
            Console.Write(String.Format("{0} ",numList[i]));
        }

        Random random = new Random();
        Console.WriteLine("\n\nRandom Order");
        for (int i = 0; i < numList.Capacity; i++)
        {
            int randomIndex = random.Next(numList.Count);
            Console.Write(String.Format("{0} ", numList[randomIndex]));
            numList.RemoveAt(randomIndex);
        }
        Console.ReadLine();

이 코드는 배열의 숫자를 섞습니다.

using System;

// ...
    static void Main(string[] args)
    {
        Console.ForegroundColor = ConsoleColor.Cyan;
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Shuffle(numbers);

        for (int i = 0; i < numbers.Length; i++)
            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
        Console.WriteLine();

        string[] words = { "this", "is", "a", "string", "of", "words" };
        Shuffle(words);

        for (int i = 0; i < words.Length; i++)
            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
        Console.WriteLine();

        Console.ForegroundColor = ConsoleColor.Gray;
        Console.Write("Press any key to quit . . . ");
        Console.ReadKey(true);
    }

    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();

        for (int i = 0; i < array.Length; i++)
        {
            T temporary = array[i];
            int intrandom = random.Next(array.Length);
            array[i] = array[intrandom];
            array[intrandom] = temporary;
        }
    }

OLINQ를 사용하는 간단한 방법은 다음과 같습니다.

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }  
    return sortedList;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top