在 C# 中随机“排序”（洗牌）整数列表的最有效方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/375351/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Most efficient way to randomly "sort" (Shuffle) a list of integers in C#
提问by Carl
I need to randomly 'sort' a list of integers (0-1999) in the most efficient way possible. Any ideas?
我需要以最有效的方式随机“排序”整数列表（0-1999）。有任何想法吗？
Currently, I am doing something like this:
目前，我正在做这样的事情：
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;
}
}
采纳答案by Greg Hewgill
A good linear-time shuffling algorithm is the Fisher-Yates shuffle.
一个好的线性时间改组算法是Fisher-Yates shuffle。
One problem you'll find with your proposed algorithm is that as you near the end of the shuffle, your loop will spend a lot of time looking for randomly chosen elements that have not yet been swapped. This may take an indeterminate amount of time once it gets to the last element to swap.
你会发现你提出的算法的一个问题是，当你接近洗牌结束时，你的循环将花费大量时间寻找尚未交换的随机选择的元素。一旦到达要交换的最后一个元素，这可能需要不确定的时间。
Also, it looks like your algorithm will never terminate if there are an odd number of elements to sort.
此外，如果要排序的元素数量为奇数，则您的算法似乎永远不会终止。
回答by Tim
To improve your efficiency you can keep a set of values/indices that have been swapped rather than a boolean for indicating they were swapped. Pick your randomized swap index from the remaining pool. When the pool is 0, or when you made it through the initial list then you are done. You don't have the potential to try to select a random swap index value.
为了提高您的效率，您可以保留一组已交换的值/索引，而不是指示它们已交换的布尔值。从剩余的池中选择您的随机交换索引。当池为 0 时，或者当您通过初始列表时，您就完成了。您没有可能尝试选择随机交换索引值。
When you do a swap, just remove them from the pool.
当您进行交换时，只需将它们从池中删除即可。
For the size of data you are looking at it is no big deal.
对于您正在查看的数据大小，这没什么大不了的。
回答by Joseph Ferris
I am not sure of the efficiency factor, but I have used something similar to the following, if you aren't opposed to using an ArrayList:
我不确定效率因素，但如果您不反对使用 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;
}
Using this, you do not have to worry about the intermediate swapping.
使用它，您不必担心中间交换。
回答by Micah
As Greg pointed out the Fisher-Yates shufflewould be the best approach. Here is an implementation of the algorithm from Wikipedia:
正如 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;
}
}
The implementation above relies on Random.nextInt(int) providing sufficiently random and unbiased results
上面的实现依赖于 Random.nextInt(int) 提供足够随机和无偏的结果
回答by Micah
Wouldn't something like this work?
不会像这样的工作吗？
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));
回答by ICR
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;
}
modified to handle lists or other objects implementing IEnumerable
修改为处理列表或其他实现 IEnumerable 的对象
回答by foson
We can make an extension method out of this to get a Random enumerator for any IList collection
我们可以从中创建一个扩展方法来为任何 IList 集合获取一个 Random 枚举器
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];
}
}
}
This uses a reverse Fisher-Yates shuffle on the indexes of the list we want to randomly enumerate through. Its a bit of a size hog (allocating 4*list.Count bytes), but runs in O(n).
这在我们想要随机枚举的列表的索引上使用反向 Fisher-Yates shuffle。它有点大（分配 4*list.Count 字节），但在 O(n) 中运行。
回答by Jim Conte
I made a method using a temporary Hashtable, allowing the Hashtable's natural key sort to randomize. Simply add, read and discard.
我使用临时 Hashtable 制作了一个方法，允许 Hashtable 的自然键排序随机化。只需添加、阅读和丢弃。
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
回答by Dmitry
itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList()
回答by Arsen Zahray
ICR's answer is very fast, but the resulting arrays aren't distributed normally. If you want a normal distribution, here's the code:
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;
}
Note that in my tests, this algorithm was 6 times slower than the one ICR provided, however this is the only way I could come up with to get a normal result distribution
请注意，在我的测试中，此算法比提供的 ICR 慢 6 倍，但这是我想出的获得正态结果分布的唯一方法
