C#中随机“排序”（洗牌）整数列表的最高效方法

Question

我需要以最有效的方式随机“排序”一个整数列表（0-1999）。 有什么想法吗？

目前，我正在做这样的事情：

bool[] bIndexSet = new bool[iItemCount];

for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++)
{
    int iSwapIndex = random.Next(iItemCount);
    if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex)
    {
        int iTemp = values[iSwapIndex];
        values[iSwapIndex] = values[iCurIndex];
        values[iCurIndex] = values[iSwapIndex];
        bIndexSet[iCurIndex] = true;
        bIndexSet[iSwapIndex] = true;
    }
}

- Carl

---

请注意，您创建了一个名为iTemp的变量，但没有使用它。这当然会导致问题。 - Aistina

啊，是的。我本来是想将值[iCurIndex]赋值为iTemp。 - Carl

更好的表达应该是：“创建整数列表的随机排列的最有效方法”。 - ICR

可能是使用.NET随机化字符串数组的最佳方法的重复问题。 - Ruben Bartelink

Answer 1

一个很好的线性时间洗牌算法是Fisher-Yates shuffle。

你提出的算法存在一个问题，当你接近洗牌结束时，你的循环将花费很多时间寻找尚未交换的随机选择元素。一旦到达最后一个要交换的元素，这可能需要不确定的时间。

此外，如果要排序的元素数量为奇数，则看起来你的算法永远不会终止。

- Greg Hewgill

---

除非算法在您的回答之后被编辑，否则在洗牌结束时不会出现减速。 iCurIndex 仅在 for 语句中赋值。然而，当 iCurIndex == iSwapIndex 时，可能会有许多未排序的元素。 - Ash

这只是一个小问题，但 Fisher-Yates 算法实际上无法达到线性复杂度，任何洗牌算法也都不行，因为要在 n! 个排列中随机选择，必须生成至少 log(n!) 位的熵。 - Owen

Answer 2

static Random random = new Random();

public static IEnumerable<T> RandomPermutation<T>(IEnumerable<T> sequence)
{
    T[] retArray = sequence.ToArray();


    for (int i = 0; i < retArray.Length - 1; i += 1)
    {
        int swapIndex = random.Next(i, retArray.Length);
        if (swapIndex != i) {
            T temp = retArray[i];
            retArray[i] = retArray[swapIndex];
            retArray[swapIndex] = temp;
        }
    }

    return retArray;
}

修改以处理列表或其他实现IEnumerable的对象

- ICR

---

为了避免 if 检查，可以使用 random.Next(i+1, array.Length)。同时需要注意 i < array.Lenth-1，因为我们不会交换相同的（即最后一个）元素。 - kolobok

旧的线程 - 但是如果有人考虑复制上面的代码 - 它不会正确地工作。列表中的第一个元素永远不会被选中 - 永远不会！ - dotnetnoob

通过使用 random.Next(i+1, array.Length)，您可以消除它与自身交换的可能性，这是提供可能性均匀分布所必需的。if语句实际上只是一个快捷方式，避免了与自身交换的工作。 - ICR

@dotnetnoob 感谢。如果我理解你的意思正确，我认为我已经修复了代码。你能确认一下吗？ - ICR

这也在MoreLinq中实现了（尽管还没有在其NuGet中发布）：http://code.google.com/p/morelinq/source/browse/MoreLinq/RandomSubset.cs - angularsen

Answer 3

我们可以将此方法制作成扩展方法，以获取任何IList集合的随机枚举器。

class Program
{
    static void Main(string[] args)
    {
        IList<int> l = new List<int>();
        l.Add(7);
        l.Add(11);
        l.Add(13);
        l.Add(17);

        foreach (var i in l.AsRandom())
            Console.WriteLine(i);

        Console.ReadLine();
    }
}


public static class MyExtensions
{
    public static IEnumerable<T> AsRandom<T>(this IList<T> list)
    {
        int[] indexes = Enumerable.Range(0, list.Count).ToArray();
        Random generator = new Random();

        for (int i = 0; i < list.Count; ++i )
        {
            int position = generator.Next(i, list.Count);

            yield return list[indexes[position]];

            indexes[position] = indexes[i];
        }
    }
}   

这个方法在列表随机枚举时使用了反向的Fisher-Yates shuffle算法对索引进行操作。虽然它需要分配4 * 列表元素数量的字节，但其时间复杂度为O(n)。

- foson

Answer 4

正如Greg所指出的，Fisher-Yates洗牌算法是最好的方法。这里是维基百科上该算法的实现：

public static void shuffle (int[] array)
{
   Random rng = new Random();   // i.e., java.util.Random.
   int n = array.length;        // The number of items left to shuffle (loop invariant).
   while (n > 1)
   {
      int k = rng.nextInt(n);  // 0 <= k < n.
      n--;                     // n is now the last pertinent index;
      int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
      array[n] = array[k];
      array[k] = temp;
   }
}

上述实现依赖于Random.nextInt(int)提供足够随机和无偏的结果。

- Micah

---

我在VB.NET中使用了这个解决方案，效果非常好！ :) 谢谢 - Mathieu G

@MathieuG 经过8年的努力，Micah终于收获了！;) - Failed Scientist

Answer 5

我不确定效率因素，但是如果您不反对使用ArrayList，我已经使用了类似以下内容的东西：

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

使用这个方法，您无需担心中间交换。

- Joseph.Ferris

---

Array.RemoveAt是一个O(n)的操作，而且循环的每次迭代都会将原始数组的大小减小1。这使得你的函数复杂度等同于从array.count到0的n的总和，即O((n^2+n)/2)。虽然可以运行，但效率并不高。 - Juliet

Answer 6

为提高效率，您可以维护一组已交换的值/索引，而不是使用布尔值来指示它们是否已被交换。从剩余池中选择随机交换索引。当池为空或者当您遍历完初始列表时，就完成了操作。这样您就不必尝试选择随机交换索引值。

进行交换时，只需将其从池中删除即可。

对于您所查看的数据大小，这并不是什么大问题。

- Tim

Answer 7

itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList()

- Dmitry

Answer 8

ICR的回答非常快，但是生成的数组不符合正态分布。如果您想要正态分布，请使用以下代码：

    public static IEnumerable<T> RandomPermutation<T>(this IEnumerable<T> sequence, int start,int end)
    {
        T[] array = sequence as T[] ?? sequence.ToArray();

        var result = new T[array.Length];

        for (int i = 0; i < start; i++)
        {
            result[i] = array[i];
        }
        for (int i = end; i < array.Length; i++)
        {
            result[i] = array[i];
        }

        var sortArray=new List<KeyValuePair<double,T>>(array.Length-start-(array.Length-end));
        lock (random)
        {
            for (int i = start; i < end; i++)
            {
                sortArray.Add(new KeyValuePair<double, T>(random.NextDouble(), array[i]));
            }
        }

        sortArray.Sort((i,j)=>i.Key.CompareTo(j.Key));

        for (int i = start; i < end; i++)
        {
            result[i] = sortArray[i - start].Value;
        }

        return result;
    }

注意，在我的测试中，这种算法比ICR提供的算法慢6倍，但这是我能想到的唯一方法来获得正常的结果分布。

- Arsen Zahray

Answer 9

关于什么：

System.Array.Sort(arrayinstance, RandomizerMethod);
...
//any evoluated random class could do it !
private static readonly System.Random Randomizer = new System.Random();

private static int RandomizerMethod<T>(T x, T y)
    where T : IComparable<T>
{
    if (x.CompareTo(y) == 0)
        return 0;

    return Randomizer.Next().CompareTo(Randomizer.Next());
}

就是这样！

- que dal

Answer 10

您可以使用一个名为ListShuffle（源代码）的NuGet包，以线程安全的方式使用Fisher-Yates算法对列表进行洗牌，并可选择使用具有密码学强度的随机数。

var myList = new List<string>();
myList.Add("Item A");
myList.Add("Item B");
myList.Add("Item C");

myList.Shuffle();

或者（性能较差但具有加密强度）

var myList = new List<string>();
myList.Add("Item A");
myList.Add("Item B");
myList.Add("Item C");

myList.CryptoStrongShuffle();

- Mark Cilia Vincenti