随机“排序”的最有效方法 （随机排列）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;
    }
}

Answer 1

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

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

另外，如果要排序的元素数量为奇数，您的算法似乎永远不会终止。

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 的对象

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 洗牌。 它的大小有点大（分配 4*list.Count 字节），但运行时间为 O(n)。

Answer 4

正如 Greg 指出的那样，Fisher-Yates shuffle 将是最好的方法。 以下是来自维基百科的算法的实现：

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) 提供
足够随机和公正
结果

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

使用这个，您不必担心中间交换。

Answer 6

为了提高效率，您可以保留一组已交换的值/索引，而不是用于指示它们已交换的布尔值。 从剩余池中选择随机交换索引。 当池为 0 时，或者当您完成初始列表时，您就完成了。 您没有可能尝试选择随机交换索引值。

当你进行交换时，只需将它们从池中删除即可。

对于您正在查看的数据大小来说，这没什么大不了的。

Answer 7

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

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 倍，但这是我能想出的获得正态结果分布的唯一方法

Answer 9

这样的事情行不通吗？

var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
var random = new Random();
list.Sort((a,b)=>random.Next(-1,1));

Answer 10

怎么样：

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

瞧！

Answer 11

这是我用过的。
这肯定不是最快的，但对于大多数情况来说它可能已经足够好了，最重要的是，它非常简单。

IEnumerable<ListItem> list = ...;
Random random = new Random(); // important to not initialize a new random in the OrderBy() function
return list.OrderBy(i => random.Next());

Answer 12

您可以使用名为 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();

Answer 13

我使用临时哈希表创建了一种方法，允许哈希表的自然键排序随机化。 只需添加、读取和丢弃即可。

int min = 1;
int max = 100;
Random random;
Hashtable hash = new Hashtable();
for (int x = min; x <= max; x++)
{
    random = new Random(DateTime.Now.Millisecond + x);
    hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x);
}
foreach (int key in hash.Keys)
{
    HttpContext.Current.Response.Write("<br/>" + hash[key] + "::" + key);
}
hash.Clear(); // cleanup