52

我需要以最有效的方式随机“排序”整数列表（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;
    }
}
4

12 回答 12

55

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

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

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

于 2008-12-17T17:37:14.687 回答
32 
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 的对象

于 2008-12-17T17:59:44.343 回答
18

我们可以从中创建一个扩展方法来获取任何 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) 中运行。

于 2008-12-17T19:55:15.563 回答
6

正如 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) 提供足够随机和无偏的结果

于 2008-12-17T17:51:33.660 回答
4

我不确定效率因素，但如果您不反对使用 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;
}

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

于 2008-12-17T17:49:39.293 回答
2

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

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

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

于 2008-12-17T17:46:19.677 回答
2 
itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList()
于 2012-12-22T21:29:53.030 回答
1

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

于 2013-08-11T13:49:48.523 回答
0

像这样的东西不会起作用吗？

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));
于 2008-12-17T17:59:30.740 回答
0

关于什么 ：

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

瞧！

于 2015-11-02T16:27:15.637 回答
0

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

IEnumerable<ListItem> list = ...;
Random random = new Random(); // important to not initialize a new random in the OrderBy() function
return list.OrderBy(i => random.Next());
于 2019-09-22T19:36:53.763 回答
-1

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

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
于 2010-03-15T14:15:00.247 回答