使用.NET 随机化数组的最佳方法

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

请在你的回答中包含一个 C # 示例。

195164 次浏览
小开

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

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

小开

随机化数组是非常复杂的，因为您必须移动一堆字符串。为什么不从数组中随机读取呢？在最坏的情况下，您甚至可以使用 getNextString ()创建一个包装器类。如果您确实需要创建一个随机数组，那么您可以这样做

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

* 5是任意的。

小开

该算法简单但效率不高，O (N2)。所有的“ order by”算法通常是 O (N logN)。对于成千上万个元素，它可能不会有什么不同，但对于大型列表就会有所不同。

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 (N2)的原因是微妙的: 列表 RemoveAt ()是一个 O (N)操作，除非您从末尾按顺序删除。

小开
最佳答案

如果你使用的是.NET 3.5，你可以使用下面的 IEnumablecool:

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

第二次编辑，回应系统评论。由于返回一个基于时间的序列，Random“不是线程安全的”和“只适合玩具应用程序”: 正如我的例子中使用的那样，Random ()是完全线程安全的，除非你允许重新输入随机化数组的例程，在这种情况下，你无论如何都需要类似于 lock (MyRandomArray)的东西来不破坏你的数据，这也将保护 rnd。

此外，应该很好地理解，系统。随机作为熵的来源并不是很强。正如在 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]);
}
小开

我突然想到，你可以这么做:

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);
}
小开 
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);
}
小开

你在找一个洗牌算法，对吧？

好吧，有两种方法可以做到这一点: 聪明但人们似乎总是误解它，并得到它错误的，所以也许它毕竟不是那么聪明的方法，和愚蠢的岩石，但谁在乎，因为它工作的方法。

愚蠢的方式

  • 创建第一个数组的副本，但是每个字符串应该标记一个随机数。
  • 根据随机数对重复数组进行排序。

这个算法工作得很好，但是要确保随机数生成器不会将两个字符串标记为相同的数字。由于所谓的 生日问题，这种情况发生的频率比您预期的要高。其时间复杂度为 O (N对数 N)。

聪明的办法

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

对大小为 N的数组进行洗牌(范围为[0.N-1]的索引) :

如果 N = 0
  • 什么都别做
如果 N > 0
  • (递归步骤) 洗牌数组的第一个 N-1元素
  • 选择范围[0.N-1]内的随机指数 X
  • 将位于索引 N-1的元素与位于索引 X的元素交换

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

时间复杂度为 O (N)。

小开

这里有一个使用 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);
小开

以下的实施方案使用了 Fisher-Yates 算法即 Knuth Shuffle。它在 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;
}
}
}

用法:

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 一样好。

小开

雅克，你的解决方案是一个定制的 IComparer 是不安全的。Sort 例程要求比较器符合几个要求，以便正常工作。其中首先是一致性。如果对同一对对象调用比较器，则必须始终返回相同的结果。(比较也必须是传递性的)。

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

对于将随机数值与每个条目相关联然后按该值排序的解决方案，这些解决方案会导致输出中的固有偏差，因为任何时候两个条目被赋予相同的数值，输出的随机性都会受到影响。(在“稳定”排序例程中，输入中的第一个将是输出中的第一个。数组。排序碰巧并不稳定，但是仍然存在基于 Quicksort 算法的分区的偏差)。

你需要考虑一下你需要多大程度的随机性。如果你正在运行一个扑克网站，你需要加密级别的随机性，以防止一个确定的攻击者，你有非常不同的要求，从某人谁只是想随机化一首歌曲播放列表。

对于歌曲列表改组，使用带种子的 PRNG (如 System)没有问题。随机)。对于一个扑克网站，它甚至不是一个选项，你需要考虑的问题比任何人都会为你做的堆栈溢出难得多。(使用加密 RNG 只是一个开始，你需要确保你的算法不会引入偏差，你有足够的熵源，并且你不会暴露任何内部状态，这会影响随后的随机性)。

小开

这篇文章已经得到了很好的回应——使用 Durstenfeld 实现的 Fisher-Yates 洗牌来得到一个快速而公正的结果。甚至还有一些实现被发布，尽管我注意到有些实际上是不正确的。

不久前，我写了几篇关于 使用此技术实现完全和部分洗牌的文章，(第二个链接是我希望增加价值的地方)还有 一篇关于如何检查你的实施是否公正的后续文章，它可以用来检查任何洗牌算法。在第二篇文章的末尾，你可以看到随机数选择中一个简单错误所造成的影响。

小开

您还可以使用 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>();
小开 
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;
}
小开

好吧，这显然是我这边的问题(对不起... ...) ，但是我经常使用一种非常通用的加密强方法。

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 ()是任何 IEnumable 的一个扩展，因此可以随机地获取从0到1000的数字

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

在排序时，这种方法也不会给人任何惊喜，因为在序列中，每个元素只生成和记住一次排序值。

小开

你不需要复杂的算法。

只有一句简单的话:

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

请注意，如果您首先不使用 List，那么首先需要将 Array转换为 List。

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

小开

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

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

可能是:

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];
}
小开 
 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;
}
}

提交答案