随机化一个List <T>
随机化C＃中通用列表的顺序的最佳方法是什么？ 我在一个列表中有一个有限的75个数字，我想分配一个随机顺序，以便为一个彩票types的应用程序绘制它们。
使用基于Fisher-Yates shuffle的扩展方法对任意(I)List进行随机播放 ：
private static Random rng = new Random(); public static void Shuffle<T>(this IList<T> list) { int n = list.Count; while (n > 1) { n--; int k = rng.Next(n + 1); T value = list[k]; list[k] = list[n]; list[n] = value; } }
用法：
List<Product> products = GetProducts(); products.Shuffle();
上面的代码使用了备受批评的System.Random方法来select交换候选项。 速度很快，但不像应该那样随机。 如果你需要更好的随机性质量，可以使用System.Security.Cryptography中的随机数生成器，如下所示：
using System.Security.Cryptography; ... public static void Shuffle<T>(this IList<T> list) { RNGCryptoServiceProvider provider = new RNGCryptoServiceProvider(); int n = list.Count; while (n > 1) { byte[] box = new byte[1]; do provider.GetBytes(box); while (!(box[0] < n * (Byte.MaxValue / n))); int k = (box[0] % n); n--; T value = list[k]; list[k] = list[n]; list[n] = value; } }
这个博客 （WayBack Machine）提供了一个简单的比较。
编辑：自从几年前写这个回答以来，很多人都给我评论或者写信给我，指出我比较中的那个愚蠢的缺陷。 他们当然是对的。 如果按照预期的方式使用System.Random没有任何问题。 在我上面的第一个例子中，我实例化了Shuffle方法中的rngvariables，如果这个方法将被重复调用，那么这个方法会很麻烦。 下面是一个固定的，完整的例子，基于今天从@weston收到的真正有用的评论。
Program.cs中：
using System; using System.Collections.Generic; using System.Threading; namespace SimpleLottery { class Program { private static void Main(string[] args) { var numbers = new List<int>(Enumerable.Range(1, 75)); numbers.Shuffle(); Console.WriteLine("The winning numbers are: {0}", string.Join(", ", numbers.GetRange(0, 5))); } } public static class ThreadSafeRandom { [ThreadStatic] private static Random Local; public static Random ThisThreadsRandom { get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + Thread.CurrentThread.ManagedThreadId))); } } } static class MyExtensions { public static void Shuffle<T>(this IList<T> list) { int n = list.Count; while (n > 1) { n--; int k = ThreadSafeRandom.ThisThreadsRandom.Next(n + 1); T value = list[k]; list[k] = list[n]; list[n] = value; } } } }
如果我们只需要以一个完全随机的顺序（只是混合列表中的项目）洗牌项目，我更喜欢这个简单而有效的代码，通过GUID订购物品…
var shuffledcards = cards.OrderBy(a => Guid.NewGuid()).ToList();
我对这个简单algorithm的所有笨重的版本感到有点惊讶。 Fisher-Yates（或Knuth shuffle）有点棘手，但非常紧凑。 如果你去维基百科，你会看到这个algorithm的版本反向循环，很多人似乎并不明白为什么它是相反的。 关键的原因是这个版本的algorithm假设随机数发生器Random(n)在你的处理有以下两个属性：
- 它接受n作为单个input参数。
- 它返回从0到n的数字。
但是.Net随机数发生器不满足＃2属性。 Random.Next(n)将返回从0到n-1的数字。 如果你尝试使用for-loop，那么你需要调用Random.Next(n+1) ，这会增加一个额外的操作。
然而，.Net随机数发生器有另外一个很好的函数Random.Next(a,b) ，它返回a到b-1（含）。 这实际上非常适合于具有正常循环的algorithm的实现。 所以，不要紧张，这是正确，高效和紧凑的实现：
public static void Shuffle<T>(this IList<T> list, Random rnd) { for(var i=0; i < list.Count; i++) list.Swap(i, rnd.Next(i, list.Count)); } public static void Swap<T>(this IList<T> list, int i, int j) { var temp = list[i]; list[i] = list[j]; list[j] = temp; }
IEnumerable的扩展方法：
public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source) { Random rnd = new Random(); return source.OrderBy<T, int>((item) => rnd.Next()); }
public static List<T> Randomize<T>(List<T> list) { List<T> randomizedList = new List<T>(); Random rnd = new Random(); while (list.Count > 0) { int index = rnd.Next(0, list.Count); //pick a random item from the master list randomizedList.Add(list[index]); //place it at the end of the randomized list list.RemoveAt(index); } return randomizedList; }
编辑 RemoveAt是我以前的版本中的一个弱点。 该解决scheme克服了这一点。
public static IEnumerable<T> Shuffle<T>( this IEnumerable<T> source, Random generator = null) { if (generator == null) { generator = new Random(); } var elements = source.ToArray(); for (var i = elements.Length - 1; i >= 0; i--) { var swapIndex = generator.Next(i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; } }
注意可选的Random generator ，如果Random generator的基本框架实现不是线程安全的或者足够强大以满足您的需要，则可以将您的实现注入到操作中。
在这个答案中可以find适合线程安全的密码强度Random实现的合适实现。
这是一个想法，以（希望）有效的方式扩展IList。
public static IEnumerable<T> Shuffle<T>(this IList<T> list) { var choices = Enumerable.Range(0, list.Count).ToList(); var rng = new Random(); for(int n = choices.Count; n > 1; n--) { int k = rng.Next(n); yield return list[choices[k]]; choices.RemoveAt(k); } yield return list[choices[0]]; }
你可以用这个简单的扩展方法来实现
public static class IEnumerableExtensions { public static IEnumerable<t> Randomize<t>(this IEnumerable<t> target) { Random r = new Random(); return target.OrderBy(x=>(r.Next())); } }
您可以通过执行以下操作来使用它
// use this on any collection that implements IEnumerable! // List, Array, HashSet, Collection, etc List<string> myList = new List<string> { "hello", "random", "world", "foo", "bar", "bat", "baz" }; foreach (string s in myList.Randomize()) { Console.WriteLine(s); }
我通常使用：
var list = new List<T> (); fillList (list); var randomizedList = new List<T> (); var rnd = new Random (); while (list.Count != 0) { var index = rnd.Next (0, list.Count); randomizedList.Add (list [index]); list.RemoveAt (index); }
如果你有一个固定的数字（75），你可以创build一个75个元素的数组，然后枚举你的列表，将元素移动到数组中的随机位置。 您可以使用Fisher-Yates shuffle生成列表号到数组索引的映射。
这是我希望不修改原文的首选洗牌方法。 它是Fisher-Yates“内外”algorithm的一个变体，可以在任何可枚举的序列上工作（ source的长度不需要从头开始）。
public static IList<T> NextList<T>(this Random r, IEnumerable<T> source) { var list = new List<T>(); foreach (var item in source) { var i = r.Next(list.Count + 1); if (i == list.Count) { list.Add(item); } else { var temp = list[i]; list[i] = item; list.Add(temp); } } return list; }
该algorithm也可以通过分配从0到length - 1的范围来实现，并通过将随机select的索引与最后一个索引交换来随机地耗尽索引，直到所有索引被精确select一次。 上面的代码完成了完全相同的事情，但没有额外的分配。 这是相当整洁。
关于Random类，它是一个通用的数字发生器（如果我正在运行一个彩票，我会考虑使用不同的东西）。 它也默认依靠基于时间的种子值。 解决这个问题的一个小小的解决办法是使用RNGCryptoServiceProvider对Random类进行种子处理，或者使用RNGCryptoServiceProvider类似于这个方法（见下面）来生成统一select的随机双浮点值，但是运行抽奖需要理解随机性和随机性来源的性质。
var bytes = new byte[8]; _secureRng.GetBytes(bytes); var v = BitConverter.ToUInt64(bytes, 0); return (double)v / ((double)ulong.MaxValue + 1);
产生一个随机双（仅在0和1之间）的点是用来缩放到一个整数解。 如果你需要从一个列表中select一个基于随机双x ，它总是0 <= x && x < 1是直截了当的。
return list[(int)(x * list.Count)];
请享用！
如果你不介意使用两个Lists ，那么这可能是最简单的方法，但可能不是最有效或不可预测的方法：
List<int> xList = new List<int>() { 1, 2, 3, 4, 5 }; List<int> deck = new List<int>(); foreach (int xInt in xList) deck.Insert(random.Next(0, deck.Count + 1), xInt);
这是一个高效的Shuffler，它返回一个混合值的字节数组。 它永远不会洗牌超过需要。 它可以从之前停止的地方重新启动。 我的实际实现（未显示）是一个MEF组件，允许用户指定的replace混洗器。
public byte[] Shuffle(byte[] array, int start, int count) { int n = array.Length - start; byte[] shuffled = new byte[count]; for(int i = 0; i < count; i++, start++) { int k = UniformRandomGenerator.Next(n--) + start; shuffled[i] = array[k]; array[k] = array[start]; array[start] = shuffled[i]; } return shuffled; }
`
这是一个线程安全的方式来做到这一点：
public static class EnumerableExtension { private static Random globalRng = new Random(); [ThreadStatic] private static Random _rng; private static Random rng { get { if (_rng == null) { int seed; lock (globalRng) { seed = globalRng.Next(); } _rng = new Random(seed); } return _rng; } } public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> items) { return items.OrderBy (i => rng.Next()); } }
public Deck(IEnumerable<Card> initialCards) { cards = new List<Card>(initialCards); public void Shuffle() } { List<Card> NewCards = new List<Card>(); while (cards.Count > 0) { int CardToMove = random.Next(cards.Count); NewCards.Add(cards[CardToMove]); cards.RemoveAt(CardToMove); } cards = NewCards; } public IEnumerable<string> GetCardNames() { string[] CardNames = new string[cards.Count]; for (int i = 0; i < cards.Count; i++) CardNames[i] = cards[i].Name; return CardNames; } Deck deck1; Deck deck2; Random random = new Random(); public Form1() { InitializeComponent(); ResetDeck(1); ResetDeck(2); RedrawDeck(1); RedrawDeck(2); } private void ResetDeck(int deckNumber) { if (deckNumber == 1) { int numberOfCards = random.Next(1, 11); deck1 = new Deck(new Card[] { }); for (int i = 0; i < numberOfCards; i++) deck1.Add(new Card((Suits)random.Next(4),(Values)random.Next(1, 14))); deck1.Sort(); } else deck2 = new Deck(); } private void reset1_Click(object sender, EventArgs e) { ResetDeck(1); RedrawDeck(1); } private void shuffle1_Click(object sender, EventArgs e) { deck1.Shuffle(); RedrawDeck(1); } private void moveToDeck1_Click(object sender, EventArgs e) { if (listBox2.SelectedIndex >= 0) if (deck2.Count > 0) { deck1.Add(deck2.Deal(listBox2.SelectedIndex)); } RedrawDeck(1); RedrawDeck(2); }
老职位肯定，但我只是使用一个GUID。
Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList();
GUID始终是唯一的，并且每次结果每次都会更新，因此它将被重新生成。
接受的答案的一个简单的修改，返回一个新的列表，而不是就地工作，并接受更一般的IEnumerable<T>和其他Linq方法一样。
private static Random rng = new Random(); /// <summary> /// Returns a new list where the elements are randomly shuffled. /// Based on the Fisher-Yates shuffle, which has O(n) complexity. /// </summary> public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) { var source = list.ToList(); int n = source.Count; var shuffled = new List<T>(n); shuffled.AddRange(source); while (n > 1) { n--; int k = rng.Next(n + 1); T value = shuffled[k]; shuffled[k] = shuffled[n]; shuffled[n] = value; } return shuffled; }
这种问题的一个非常简单的方法是在列表中使用一些随机元素交换。
在伪代码中，这看起来像这样：
do r1 = randomPositionInList() r2 = randomPositionInList() swap elements at index r1 and index r2 for a certain number of times
