使用。net随机化数组的最佳方法

What is the best way to randomize an array of strings with .NET? My array contains about 500 strings and I'd like to create a new Array with the same strings but in a random order.

用。net随机化字符串数组的最好方法是什么?我的数组包含大约500个字符串，我想用相同的字符串创建一个新的数组，但顺序是随机的。

Please include a C# example in your answer.

请在你的答案中包含一个c#示例。

18 个解决方案

#1

If you're on .NET 3.5, you can use the following IEnumerable coolness (VB.NET, not C#, but the idea should be clear...):

如果你在。net 3.5上，你可以使用下面的IEnumerable接口(VB)。NET，不是c#，但是想法应该是清楚的…

Random rnd=new Random();string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();    

Edit: OK and here's the corresponding VB.NET code:

编辑:好的，这是对应的VB。NET代码:

Dim rnd As New System.RandomDim MyRandomArray = MyArray.OrderBy(Function() rnd.Next)

Second edit, in response to remarks that System.Random "isn't threadsafe" and "only suitable for toy apps" due to returning a time-based sequence: as used in my example, Random() is perfectly thread-safe, unless you're allowing the routine in which you randomize the array to be re-entered, in which case you'll need something like lock (MyRandomArray) anyway in order not to corrupt your data, which will protect rnd as well.

第二编辑，回应系统的评论。随机”并不是线程安全的”和“只适合玩具应用程序”将返回一个基于时间序列:在我的示例中,使用的随机()是完全线程安全的,除非你允许的程序重新进入随机化数组,在这种情况下,你需要像锁(MyRandomArray)为了不破坏你的数据,这将保护研发。

Also, it should be well-understood that System.Random as a source of entropy isn't very strong. As noted in the MSDN documentation, you should use something derived from System.Security.Cryptography.RandomNumberGenerator if you're doing anything security-related. For example:

此外，应该充分理解这一制度。作为熵源的随机性不是很强。正如MSDN文档中提到的，您应该使用System.Security.Cryptography中派生出来的东西。如果您正在做任何与安全性相关的事情，请使用RandomNumberGenerator。例如:

using System.Security.Cryptography;

...

…

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

…

static int GetNextInt32(RNGCryptoServiceProvider rnd)    {        byte[] randomInt = new byte[4];        rnd.GetBytes(randomInt);        return Convert.ToInt32(randomInt[0]);    }

#2

The following implementation uses the Fisher-Yates algorithm. It runs in O(n) time and shuffles in place, so is better performing than the 'sort by random' technique, although it is more lines of code. See here for some comparative performance measurements. I have used System.Random, which is fine for non-cryptographic purposes.*

下面的实现使用Fisher-Yates算法。它运行在O(n)时间和洗牌中，因此比“排序随机”技术更好，尽管它是更多的代码行。请参阅这里的一些比较性能度量。我已经使用系统。对于非加密目的而言，这是可以的

static class RandomExtensions{    public static void Shuffle<T> (this Random rng, T[] array)    {        int n = array.Length;        while (n > 1)         {            int k = rng.Next(n--);            T temp = array[n];            array[n] = array[k];            array[k] = temp;        }    }}

Usage:

用法:

var array = new int[] {1, 2, 3, 4};new Random().Shuffle(array);

* For longer arrays, in order to make the (extremely large) number of permutations equally probable it would be necessary to run a pseudo-random number generator (PRNG) through many iterations for each swap to produce enough entropy. For a 500-element array only a very small fraction of the possible 500! permutations will be possible to obtain using a PRNG. Nevertheless, the Fisher-Yates algorithm is unbiased and therefore the shuffle will be as good as the RNG you use.

*对于较长的数组，为了使(非常大的)排列数目相等，需要对每个交换进行多次迭代运行伪随机数生成器(PRNG)，以产生足够的熵。对于一个500元素的数组来说，这只是可能的500元素的很小一部分!使用PRNG可以获得排列。尽管如此，Fisher-Yates算法是无偏见的，因此洗牌将和你使用的RNG一样好。

#3

You're looking for a shuffling algorithm, right?

你在寻找一个变换算法，对吧?

Okay, there are two ways to do this: the clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after-all way, and the dumb-as-rocks-but-who-cares-because-it-works way.

好吧，有两种方法可以做到这一点:一种是聪明的但却总是对自己的想法产生误解的方法，另一种是愚蠢的- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -的方法。

Dumb way

• Create a duplicate of your first array, but tag each string should with a random number.
• 创建第一个数组的副本，但是为每个字符串标记一个随机数。
• Sort the duplicate array with respect to the random number.
• 根据随机数对重复数组进行排序。

This algorithm works well, but make sure that your random number generator is unlikely to tag two strings with the same number. Because of the so-called Birthday Paradox, this happens more often than you might expect. Its time complexity is O(n log n).

这个算法运行得很好，但是请确保您的随机数生成器不太可能将两个字符串标记为相同的数字。由于所谓的“生日悖论”，这种情况发生的频率比你想象的要高。它的时间复杂度是O(n log n)

Clever way

I'll describe this as a recursive algorithm:

我将把它描述为一个递归算法:

To shuffle an array of size n (indices in the range [0..n-1]):

洗牌大小为n的数组(范围内的索引[0..n-1]):

if n = 0

• do nothing
• 什么都不做

if n > 0

• (recursive step) shuffle the first n-1 elements of the array
• (递归步骤)对数组中的第一个n-1元素进行洗牌。
• choose a random index, x, in the range [0..n-1]
• 在[0..n-1]范围内选择一个随机指标x
• swap the element at index n-1 with the element at index x
• 将索引n-1的元素与索引x的元素交换

The iterative equivalent is to walk an iterator through the array, swapping with random elements as you go along, but notice that you cannot swap with an element after the one that the iterator points to. This is a very common mistake, and leads to a biased shuffle.

迭代的等效方法是遍历迭代器遍历数组，并在执行过程中使用随机元素进行交换，但是请注意，不能在迭代器指向的元素之后使用元素进行交换。这是一个非常常见的错误，并导致一个有偏见的洗牌。

Time complexity is O(n).

时间复杂度是O(n)。

#4

This algorithm is simple but not efficient, O(N²). All the "order by" algorithms are typically O(N log N). It probably doesn't make a difference below hundreds of thousands of elements but it would for large lists.

该算法简单，但效率不高。所有的“order by”算法都是典型的O(N log N)，它可能不会在成千上万的元素下产生差异，但是对于大的列表来说是如此。

var stringlist = ... // add your values to stringlistvar r = new Random();var res = new List<string>(stringlist.Count);while (stringlist.Count >0){   var i = r.Next(stringlist.Count);   res.Add(stringlist[i]);   stringlist.RemoveAt(i);}

The reason why it's O(N²) is subtle: List.RemoveAt() is a O(N) operation unless you remove in order from the end.

它是O(N2)的原因很微妙:List.RemoveAt()是O(N)操作，除非从末尾按顺序删除。

#5

You can also make an extention method out of Matt Howells. Example.

你也可以用Matt Howells来做一个扩展方法。的例子。

   namespace System    {        public static class MSSystemExtenstions        {            private static Random rng = new Random();            public static void Shuffle<T>(this T[] array)            {                rng = new Random();                int n = array.Length;                while (n > 1)                {                    int k = rng.Next(n);                    n--;                    T temp = array[n];                    array[n] = array[k];                    array[k] = temp;                }            }        }    }

Then you can just use it like:

然后你可以这样使用:

        string[] names = new string[] {                "Aaron Moline1",                 "Aaron Moline2",                 "Aaron Moline3",                 "Aaron Moline4",                 "Aaron Moline5",                 "Aaron Moline6",                 "Aaron Moline7",                 "Aaron Moline8",                 "Aaron Moline9",             };        names.Shuffle<string>();

#6

Randomizing the array is intensive as you have to shift around a bunch of strings. Why not just randomly read from the array? In the worst case you could even create a wrapper class with a getNextString(). If you really do need to create a random array then you could do something like

随机化数组是密集的，因为你必须移动一串字符串。为什么不从数组中随机读取呢?在最坏的情况下，您甚至可以使用getNextString()创建一个包装类。如果你确实需要创建一个随机数组，那么你可以做一些类似的事情

for i = 0 -> i= array.length * 5   swap two strings in random places

The *5 is arbitrary.

* 5是任意的。

#7

Just thinking off the top of my head, you could do this:

想想我的头顶，你可以这么做:

public string[] Randomize(string[] input){  List<string> inputList = input.ToList();  string[] output = new string[input.Length];  Random randomizer = new Random();  int i = 0;  while (inputList.Count > 0)  {    int index = r.Next(inputList.Count);    output[i++] = inputList[index];    inputList.RemoveAt(index);  }  return (output);}

#8

This post has already been pretty well answered - use a Durstenfeld implementation of the Fisher-Yates shuffle for a fast and unbiased result. There have even been some implementations posted, though I note some are actually incorrect.

这篇文章已经得到了很好的回答——使用Durstenfeld的Fisher-Yates洗牌实现一个快速、无偏见的结果。甚至已经发布了一些实现，尽管我注意到有些实际上是错误的。

I wrote a couple of posts a while back about implementing full and partial shuffles using this technique, and (this second link is where I'm hoping to add value) also a follow-up post about how to check whether your implementation is unbiased, which can be used to check any shuffle algorithm. You can see at the end of the second post the effect of a simple mistake in the random number selection can make.

我写了一些文章,关于使用这种技术,实现完全和部分打乱和(第二个链接是我希望添加值)也是一个后续篇关于如何检查是否公正的实现,可用于检查任何调整算法。你可以在第二篇文章的结尾看到随机数字选择中一个简单错误的影响。

#9

Generate an array of random floats or ints of the same length. Sort that array, and do corresponding swaps on your target array.

生成相同长度的随机浮点数或整数数组。对该数组进行排序，并对目标数组进行相应的交换。

This yields a truly independent sort.

这就产生了真正独立的类型。

#10

Random r = new Random();List<string> list = new List(originalArray);List<string> randomStrings = new List();while(list.Count > 0){int i = r.Random(list.Count);randomStrings.Add(list[i]);list.RemoveAt(i);}

#11

Jacco, your solution ising a custom IComparer isn't safe. The Sort routines require the comparer to conform to several requirements in order to function properly. First among them is consistency. If the comparer is called on the same pair of objects, it must always return the same result. (the comparison must also be transitive).

雅科，你为顾客提供的解决方案并不安全。排序例程要求比较器符合几个需求，以便正常工作。首先是一致性。如果在同一对对象上调用比较器，它必须总是返回相同的结果。(这种比较也必须是传递性的)。

Failure to meet these requirements can cause any number of problems in the sorting routine including the possibility of an infinite loop.

如果不能满足这些要求，排序例程中可能会出现许多问题，包括无限循环的可能性。

Regarding the solutions that associate a random numeric value with each entry and then sort by that value, these are lead to an inherent bias in the output because any time two entries are assigned the same numeric value, the randomness of the output will be compromised. (In a "stable" sort routine, whichever is first in the input will be first in the output. Array.Sort doesn't happen to be stable, but there is still a bias based on the partitioning done by the Quicksort algorithm).

对于将随机数字值与每个条目相关联，然后按该值进行排序的解决方案，这些解决方案会导致输出中的固有偏差，因为每当两个条目被分配为相同的数值时，输出的随机性就会受到影响。(在“稳定”排序例程中，输入中的第一个将在输出中第一个出现。数组中。排序并不是稳定的，但是基于快速排序算法完成的分区仍然存在偏差)。

You need to do some thinking about what level of randomness you require. If you are running a poker site where you need cryptographic levels of randomness to protect against a determined attacker you have very different requirements from someone who just wants to randomize a song playlist.

你需要考虑一下你需要多大程度的随机性。如果你运行的是一个扑克网站，你需要密码级别的随机性来保护自己不受一个确定的攻击者的攻击，那么你和那些只想随机播放歌曲的人有非常不同的要求。

For song-list shuffling, there's no problem using a seeded PRNG (like System.Random). For a poker site, it's not even an option and you need to think about the problem a lot harder than anyone is going to do for you on *. (using a cryptographic RNG is only the beginning, you need to ensure that your algorithm doesn't introduce a bias, that you have sufficient sources of entropy, and that you don't expose any internal state that would compromise subsequent randomness).

对于歌曲列表变换，使用种子PRNG(比如System.Random)是没有问题的。对于一个扑克网站来说，它甚至不是一个选项，你需要比*网站上的任何人都更难思考这个问题。(使用密码RNG仅仅是开始，您需要确保您的算法不引入偏差，确保您有足够的熵源，并且不公开任何可能危及后续随机性的内部状态)。

#12

Ok, this is clearly a bump from my side (apologizes...), but I often use a quite general and cryptographically strong method.

好吧，这显然是我这边的问题(抱歉…)，但我经常使用一个非常通用的、密码很强的方法。

public static class EnumerableExtensions{    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)    {        var randomIntegerBuffer = new byte[4];        Func<int> rand = () =>                             {                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);                             };        return from item in enumerable               let rec = new {item, rnd = rand()}               orderby rec.rnd               select rec.item;    }}

Shuffle() is an extension on any IEnumerable so getting, say, numbers from 0 to 1000 in random order in a list can be done with

Shuffle()是对任何IEnumerable的扩展，因此，例如，可以按照列表中的随机数顺序从0到1000进行排序

Enumerable.Range(0,1000).Shuffle().ToList()

This method also wont give any surprises when it comes to sorting, since the sort value is generated and remembered exactly once per element in the sequence.

这种方法在排序时也不会带来任何惊喜，因为排序值是生成的，并且在序列中的每个元素中只被记住一次。

#13

You don't need complicated algorithms.

你不需要复杂的算法。

Just one simple line:

只是一个简单的线:

Random random = new Random();array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

Note that we need to convert the Array to a List first, if you don't use List in the first place.

注意，我们需要首先将数组转换为列表，如果您不首先使用列表的话。

Also, mind that this is not efficient for very large arrays! Otherwise it's clean & simple.

另外，请注意，对于非常大的数组来说，这不是有效的!否则它是干净和简单的。

#14

This is a complete working Console solution based on the example provided in here:

这是一个完整的工作控制台解决方案，基于这里提供的示例:

class Program{    static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };    static void Main()    {        var result = Shuffle(words1);        foreach (var i in result)        {            Console.Write(i + " ");        }        Console.ReadKey();    }   static string[] Shuffle(string[] wordArray) {        Random random = new Random();        for (int i = wordArray.Length - 1; i > 0; i--)        {            int swapIndex = random.Next(i + 1);            string temp = wordArray[i];            wordArray[i] = wordArray[swapIndex];            wordArray[swapIndex] = temp;        }        return wordArray;    }         }

#15

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};        List<int> numList = new List<int>();        numList.AddRange(numbers);        Console.WriteLine("Original Order");        for (int i = 0; i < numList.Count; i++)        {            Console.Write(String.Format("{0} ",numList[i]));        }        Random random = new Random();        Console.WriteLine("\n\nRandom Order");        for (int i = 0; i < numList.Capacity; i++)        {            int randomIndex = random.Next(numList.Count);            Console.Write(String.Format("{0} ", numList[randomIndex]));            numList.RemoveAt(randomIndex);        }        Console.ReadLine();

#16

This code shuffles numbers in an array.

这段代码在数组中排列数字。

using System;// ...    static void Main(string[] args)    {        Console.ForegroundColor = ConsoleColor.Cyan;        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };        Shuffle(numbers);        for (int i = 0; i < numbers.Length; i++)            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));        Console.WriteLine();        string[] words = { "this", "is", "a", "string", "of", "words" };        Shuffle(words);        for (int i = 0; i < words.Length; i++)            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));        Console.WriteLine();        Console.ForegroundColor = ConsoleColor.Gray;        Console.Write("Press any key to quit . . . ");        Console.ReadKey(true);    }    static void Shuffle<T>(T[] array)    {        Random random = new Random();        for (int i = 0; i < array.Length; i++)        {            T temporary = array[i];            int intrandom = random.Next(array.Length);            array[i] = array[intrandom];            array[intrandom] = temporary;        }    }

#17

Here's a simple way using OLINQ:

使用OLINQ有一个简单的方法:

// Input arrayList<String> lst = new List<string>();for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());// Output arrayList<String> lstRandom = new List<string>();// RandomizeRandom rnd = new Random();lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

#18

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