使用 .NET 随机化字符串数组的最佳方法是什么？我的数组包含大约 500 个字符串，我想创建一个Array具有相同字符串但顺序随机的新数组。
请在您的答案中包含一个 C# 示例。
Matthias
问问题
179571 次
19 回答
242
下面的实现使用Fisher-Yates 算法AKA Knuth Shuffle。它在 O(n) 时间内运行并在适当的位置随机播放，因此比“随机排序”技术性能更好，尽管它的代码行数更多。有关一些比较性能测量，请参见此处。我使用了 System.Random，它适用于非加密目的。*
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;
}
}
}
用法：
var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle
* 对于更长的数组，为了使（极大）数量的排列具有同样的可能性，有必要通过多次迭代运行伪随机数生成器 (PRNG) 以产生足够的熵。对于一个 500 个元素的数组，只有可能的 500 个元素的一小部分！使用 PRNG 可以获得排列。尽管如此，Fisher-Yates 算法是公正的，因此随机播放将与您使用的 RNG 一样好。
于 2008-09-21T08:51:46.963 回答
208
如果您使用的是 .NET 3.5，则可以使用以下 IEnumerable 酷炫：
Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();
编辑：这是相应的 VB.NET 代码：
Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()
第二次编辑，回应 System.Random “不是线程安全的”和“仅适用于玩具应用程序”由于返回基于时间的序列的评论：正如我的示例中使用的那样，Random() 是完全线程安全的，除非您允许重新输入随机化数组的例程，在这种情况下，您将需要类似的东西lock (MyRandomArray)，以免损坏您的数据，这也将保护您的数据rnd。
此外，应该很好理解 System.Random 作为熵的来源不是很强。如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]);
}
于 2008-09-20T17:40:06.357 回答
19
你正在寻找一个洗牌算法，对吧？
好的，有两种方法可以做到这一点：聪明但人们总是似乎误解了它并且得到了它错了所以也许它不是那么聪明毕竟方式，以及像石头一样愚蠢但谁在乎，因为它有效的方式。
笨方法
- 创建第一个数组的副本，但每个字符串都应使用随机数标记。
- 根据随机数对重复数组进行排序。
此算法运行良好，但请确保您的随机数生成器不太可能用相同的数字标记两个字符串。由于所谓的生日悖论，这种情况发生的频率比您预期的要多。它的时间复杂度是 O( n log n )。
聪明的方式
我将其描述为递归算法：
洗牌一个大小为n的数组（索引在 [0.. n -1] 范围内）：
如果n = 0如果n > 0
- 没做什么
- （递归步骤）打乱数组的前n -1 个元素
- 在 [0.. n -1]范围内选择一个随机索引x
- 将索引n -1 处的元素与索引x处的元素交换
等效的迭代是遍历数组，在进行过程中与随机元素交换，但请注意，不能与迭代器指向的元素之后的元素交换。这是一个非常常见的错误，并导致有偏见的洗牌。
时间复杂度为 O( n )。
于 2008-09-20T17:54:15.263 回答
8
该算法简单但效率不高，O(N 2 )。所有“order by”算法通常都是 O(N log N)。它可能在数十万个元素以下没有什么区别，但对于大型列表来说会。
var stringlist = ... // add your values to stringlist
var 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);
}
它是 O(N 2 ) 的原因很微妙：List.RemoveAt()是一个 O(N) 操作，除非您从最后按顺序删除。
于 2008-09-20T17:39:27.467 回答
4
您还可以使用 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;
}
}
}
}
然后你可以像这样使用它：
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>();
于 2010-08-18T15:45:00.240 回答
2
只是想到我的头顶，你可以这样做：
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);
}
于 2008-09-20T17:42:21.390 回答
1
随机化数组是密集的，因为您必须在一堆字符串周围移动。为什么不从数组中随机读取？在最坏的情况下，您甚至可以使用 getNextString() 创建一个包装类。如果您确实需要创建一个随机数组，那么您可以执行类似的操作
for i = 0 -> i= array.length * 5
swap two strings in random places
*5 是任意的。
于 2008-09-20T17:38:46.610 回答
1
好的，这显然是我的一个问题（道歉......），但我经常使用一种非常通用且密码学强大的方法。
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() 是任何 IEnumerable 的扩展，因此可以通过以下方式在列表中以随机顺序获取从 0 到 1000 的数字
Enumerable.Range(0,1000).Shuffle().ToList()
这种方法在排序时也不会产生任何意外，因为排序值是在序列中的每个元素生成和记忆一次。
于 2012-10-24T15:37:06.313 回答
0
生成相同长度的随机浮点数或整数数组。对该数组进行排序，并对目标数组进行相应的交换。
这产生了一个真正独立的排序。
于 2008-09-20T17:37:36.583 回答
0
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);
}
于 2008-09-20T17:43:31.810 回答
0
Jacco，您使用自定义 IComparer 的解决方案并不安全。排序例程要求比较器符合几个要求才能正常运行。其中首先是一致性。如果在同一对对象上调用比较器，则它必须始终返回相同的结果。（比较也必须是传递的）。
未能满足这些要求可能会导致排序例程中出现许多问题，包括可能出现无限循环。
关于将随机数值与每个条目相关联然后按该值排序的解决方案，这些会导致输出中存在固有偏差，因为任何时候为两个条目分配相同的数值，输出的随机性都会受到影响。（在“稳定”排序例程中，输入中的第一个将是输出中的第一个。Array.Sort 碰巧不是稳定的，但仍然存在基于 Quicksort 算法完成的分区的偏差）。
您需要考虑一下您需要什么级别的随机性。如果您正在运行一个扑克网站，您需要加密级别的随机性来防止一个坚定的攻击者，您与只想随机化歌曲播放列表的人有非常不同的要求。
对于歌曲列表改组，使用种子 PRNG（如 System.Random）没有问题。对于扑克网站，它甚至不是一个选项，你需要比任何人在 stackoverflow 上为你做的更难思考这个问题。（使用加密 RNG 只是开始，您需要确保您的算法不会引入偏差，您有足够的熵源，并且您不会暴露任何会损害后续随机性的内部状态）。
于 2008-09-21T13:36:08.777 回答
0
这篇文章已经得到了很好的回答 - 使用 Fisher-Yates shuffle 的 Durstenfeld 实现来获得快速且公正的结果。甚至已经发布了一些实现，尽管我注意到有些实际上是不正确的。
不久前我写了几篇关于使用这种技术实现完全和部分洗牌的帖子，并且（这第二个链接是我希望增加价值的地方）还有一篇关于如何检查你的实现是否公正的后续帖子，可用于检查任何洗牌算法。您可以在第二篇文章的末尾看到随机数选择中的一个简单错误可能产生的影响。
于 2008-09-21T17:37:30.177 回答
0
你不需要复杂的算法。
就这么简单的一行：
Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();
请注意，如果您一开始不使用，我们需要将其转换Array为第一个。ListList
另外，请注意，这对于非常大的阵列效率不高！否则它很干净和简单。
于 2015-04-13T20:43:05.287 回答
0
这是一个完整的工作控制台解决方案，基于此处提供的示例：
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;
}
}
于 2016-04-13T16:45:33.717 回答
0
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();
于 2017-02-06T18:01:22.503 回答
0
可能：
Random random = new();
string RandomWord()
{
const string CHARS = "abcdefghijklmnoprstuvwxyz";
int n = random.Next(CHARS.Length);
return string.Join("", CHARS.OrderBy(x => random.Next()).ToArray())[0..n];
}
于 2021-12-02T16:43:49.893 回答
0
public static void Shuffle(object[] arr)
{
Random rand = new Random();
for (int i = arr.Length - 1; i >= 1; i--)
{
int j = rand.Next(i + 1);
object tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
于 2022-02-03T15:27:32.137 回答
-1
这是使用 OLINQ 的一种简单方法：
// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());
// Output array
List<String> lstRandom = new List<string>();
// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);
于 2008-09-20T19:03:07.517 回答
-1
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;
}
于 2012-05-01T12:00:09.090 回答