[C#] Random 및 OrderBy를 사용하는 것이 좋은 셔플 알고리즘입니까?

내가 좋아하는 셔플 방법이 아닙니다. 주로 O (n log n)이기 때문에 O (n) 셔플을 쉽게 구현 할 수있는 좋은 이유가 없습니다. 문제의 코드는 기본적으로 각 요소에 임의의 (희망적으로 고유 한) 숫자를 부여한 다음 해당 숫자에 따라 요소를 정렬하여 “작동”합니다.

나는 Durstenfield의 Fisher-Yates 셔플 변형을 선호 합니다.

간단한 Shuffle확장 방법을 구현하는 것은 기본적으로 Fisher-Yates의 기존 구현을 사용하여 호출 ToList하거나 ToArray입력 하는 것으로 구성됩니다 . ( Random일반적으로 인생을 더 좋게하기 위해 매개 변수로 전달하십시오.) 주변에는 많은 구현이 있습니다 … 아마도 어딘가에 답변이 있습니다.

그러한 확장 방법의 좋은 점은 독자가 실제로하려는 일을 독자에게 분명히 알 수 있다는 것입니다.

편집 : 다음은 간단한 구현입니다 (오류 검사 없음).

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length-1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

편집 : 아래 성능에 대한 의견은 요소를 섞을 때 실제로 요소를 반환 할 수 있음을 상기시킵니다.

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        // ... except we don't really need to swap it fully, as we can
        // return it immediately, and afterwards it's irrelevant.
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

이제 필요한만큼만 작업 할 수 있습니다.

두 경우 모두 Random다음과 같이 사용 하는 인스턴스에주의해야합니다 .

• Random대략 같은 시간에 두 개의 인스턴스를 생성 하면 동일한 방식으로 사용될 때 동일한 난수 시퀀스가 ​​생성됩니다.
• Random 스레드 안전하지 않습니다.

나는이 에 대한 기사Random 이러한 문제에 대한 자세한 내용이수록 및 솔루션을 제공하는합니다.

답변

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length - 1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
        // we don't actually perform the swap, we can forget about the
        // swapped element because we already returned it.
    }

    // there is one item remaining that was not returned - we return it now
    yield return elements[0];
}

OrderBy(x => r.Next(int.MaxValue))

static public class FisherYates
{
        //      Based on Java code from wikipedia:
        //      http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
        static public void Shuffle(int[] deck)
        {
                Random r = new Random();
                for (int n = deck.Length - 1; n > 0; --n)
                {
                        int k = r.Next(n+1);
                        int temp = deck[n];
                        deck[n] = deck[k];
                        deck[k] = temp;
                }
        }
}

using (var rng = new RNGCryptoServiceProvider())
{
    var data = new byte[4];
    yourCollection = yourCollection.Shuffle(rng, data);
}

/// <summary>
/// Shuffles the elements of a sequence randomly.
/// </summary>
/// <param name="source">A sequence of values to shuffle.</param>
/// <param name="rng">An instance of a random number generator.</param>
/// <param name="data">A placeholder to generate random bytes into.</param>
/// <returns>A sequence whose elements are shuffled randomly.</returns>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data)
{
    var elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        rng.GetBytes(data);
        var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}