最好的方式来随机阵列。净

StackOverflow https://stackoverflow.com/questions/108819

题

什么是最好的方式来随机的字符串数组。净?我的阵列包含大约500个字符串的和我想创建一个新的 Array 同串但是，在一个随机单。

请包括C#例在你的答案。

有帮助吗？

解决方案

如果你使用的是.NET 3.5，你可以使用以下IEnumerable酷（VB.NET，而不是C＃，但想法应该是明确的......）：

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

其他提示

以下实现使用 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一样好。

你正在寻找一个洗算法，对吗？

好吧，有两种方式来这样做：的clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after-所有的方式，和愚蠢的-因为-石头-但是谁在乎-因为它的工作方式。

愚蠢的方式

  • 创建一个重复你的第一次阵列，但标记的每个字符串应有一个随机的数量。
  • 排序的重复列相对于随机数。

这个算法的工作良好，但要确保你的随机数发生器是不可能的标记两个字相同的号码。因为所谓 生日悖论, ，这种情况往往比你想象的。其次是(n 日志 n).

聪明的办法

我将其描述为一种递归算法：

洗牌一系列大小 n (指数的范围[0..n-1]):

如果 n = 0
  • 什么也不做
如果 n > 0
  • (递归的步骤) 洗牌的第一个 n-1元件阵列
  • 随机选择一个指标， x, 在范围[0..n-1]
  • 换元件的索引 n-1的元件的索引 x

迭代相当于是一个迭代过阵列，交换与随机因素，因为你走，但是注意到你不能交换与一个元素 后 一个迭代。这是一个很常见的错误，导致了偏见的洗牌。

是(n).

该算法简单但效率不高，O（N 2 ）。所有“按顺序”算法通常为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）操作，除非你从头开始按顺序删除。

您也可以使用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>();

随机化数组是非常密集的，因为你必须转移一堆字符串。为什么不随机从数组中读取？在最坏的情况下，您甚至可以使用getNextString（）创建一个包装类。如果你真的需要创建一个随机数组，那么你可以做类似

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

* 5是任意的。

只要想到我的头脑，你就可以做到这一点：

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

Jacco，您的解决方案是自定义IComparer是不安全的。 Sort例程要求比较器符合多个要求才能正常运行。首先是一致性。如果在同一对对象上调用比较器，则它必须始终返回相同的结果。 （比较也必须是可传递的）。

未能满足这些要求会导致排序例程中出现任何问题，包括无限循环的可能性。

关于将随机数值与每个条目相关联然后按该值排序的解决方案，这些导致输出中的固有偏差，因为任何时候两个条目被分配相同的数值，输出的随机性将妥协。 （在“稳定”排序例程中，输入中的第一个将是输出中的第一个.Array.Sort不会发生稳定，但仍然存在基于Quicksort算法完成的分区的偏差）

您需要考虑一下您需要的随机性级别。如果您正在运行一个扑克网站，您需要加密级别的随机性以防止确定的攻击者，那么您只需要想要随机化歌曲播放列表的人就会有非常不同的要求。

对于歌曲列表改组，使用种子PRNG（如System.Random）没有问题。对于一个扑克网站来说，它甚至都不是一个选项，你需要在堆栈溢出上比任何人为你做的事情想得更困难。 （使用加密RNG只是一个开始，您需要确保您的算法不会引入偏差，您有足够的熵源，并且您不会暴露任何会影响后续随机性的内部状态。）

这篇文章已经得到了很好的回答 - 使用Durstenfeld对Fisher-Yates shuffle的实现来获得快速且无偏见的结果。甚至已经发布了一些实现，但我注意到一些实际上是不正确的。

我前后写了几篇关于使用这种技术实现完全和部分shuffle ，并且（第二个链接是我希望增加值的地方）后续帖子如何检查您的实现是否是无偏的，可用于检查任何随机播放算法。您可以在第二篇文章的末尾看到随机数选择中的一个简单错误的影响。

好的，这显然是我身边的一个颠簸（道歉......），但我经常使用一种非常通用且加密性强的方法。

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

这种方法在排序方面也不会给出任何意外，因为排序值会在序列中的每个元素生成并记住一次。

您不需要复杂的算法。

只需一个简单的界限： 

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

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

另外，请注意，这对于非常大的数组来说效率不高！否则它是干净的＆amp;简单。

这是一个基于此处提供的示例：

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

此代码在数组中随机播放数字。

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

这是使用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);

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;
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top