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;
}
}
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;
}
}
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;
}
}
}
}
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;
}
6
IEnumerable的扩展方法:
public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
Random rnd = new Random();
return source.OrderBy<T, int>((item) => rnd.Next());
}
3
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;
}
-5
EDITRemoveAt 是我之前版本的一个弱点 . 该解决方案克服了这一点 .
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 的基本框架实现不是线程安全的或加密强度足以满足您的需要,您可以将您的实现注入操作 .
这是一个想法,以(希望)有效的方式扩展IList . public static IEnumerable <T> Shuffle <T>(此IList <T>列表) { 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); 收益率表[choice [k]]; choices.RemoveAt(K); }
收益率表[choice [0]]; }
88
您可以使用这种简单的扩展方法来实现
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);
}
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;
}
关于 Random 类,'s a general purpose number generator (and If I was running a lottery I'd考虑使用不同的东西) . 默认情况下,它还依赖于基于时间的种子值 . 问题的一个小缓解是使用 RNGCryptoServiceProvider 播种 Random 类,或者你可以在类似于此方法的方法中使用 RNGCryptoServiceProvider (见下文)来生成统一选择的随机双浮点值,但运行抽奖几乎需要了解随机性和随机源的本质 .
var bytes = new byte[8];
_secureRng.GetBytes(bytes);
var v = BitConverter.ToUInt64(bytes, 0);
return (double)v / ((double)ulong.MaxValue + 1);
生成随机双精度(仅在0和1之间)的点是用于缩放到整数解 . 如果你需要从一个列表中选择一个基于随机双 x 的东西,它总是 0 <= x && x < 1 是直截了当的 .
return list[(int)(x * list.Count)];
请享用!
10
如果您不介意使用两个 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);
2
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);
}
3
想法是通过项目和随机顺序获得无关的对象,然后按此顺序重新排序项目并返回值:
var result = items.Select(x => new { value = x, order = rnd.Next() })
.OrderBy(x => x.order).Select(x => x.value).ToList()
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;
}
`
0
这是一种线程安全的方法:
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());
}
}
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;
}
18 回答
使用基于Fisher-Yates shuffle的扩展方法随机播放任何
(I)List
:用法:
上面的代码使用备受批评的System.Random方法来选择交换候选者 . 它速度快但不随意 . 如果你需要在shuffle中使用更好的随机性质,请使用System.Security.Cryptography中的随机数生成器,如下所示:
有一个简单的比较at this blog(WayBack Machine) .
编辑:自从几年前写下这个答案以来,很多人都评论或写信给我,指出我比较中的一个很大的愚蠢缺陷 . 他们当然是对的 . System.Random没有任何问题,如果按照预期的方式使用它 . 在我上面的第一个例子中,我在Shuffle方法中实例化了rng变量,如果要重复调用该方法,则会遇到麻烦 . 下面是一个固定的完整示例,基于今天在@weston上收到的关于SO的非常有用的评论 .
Program.cs中:
如果我们只需要以完全随机的顺序混洗项目(只是为了混合列表中的项目),我更喜欢这个简单而有效的代码,通过guid命令项目...
我似乎真的明白为什么反过来了 . 关键原因是这个版本的算法假定您使用的随机数生成器
Random(n)
具有以下两个属性:它接受n作为单个输入参数 .
它返回从0到n的数字 .
但.Net随机数生成器不满足#2属性 .
Random.Next(n)
而是返回从0到n-1的数字 . 如果您尝试反向使用for循环,则需要调用Random.Next(n+1)
,这会添加一个额外的操作 .但是,.Net随机数生成器还有另一个很好的函数
Random.Next(a,b)
,返回a到b-1(含) . 这实际上非常适合具有正常for循环的此算法的实现 . 所以不用多说,这是正确,高效和紧凑的实现:IEnumerable的扩展方法:
EDIT
RemoveAt
是我之前版本的一个弱点 . 该解决方案克服了这一点 .注意可选
Random generator
,如果Random
的基本框架实现不是线程安全的或加密强度足以满足您的需要,您可以将您的实现注入操作 .A suitable implementation for a thread-safe cryptographically strong Random implementation can be found in this answer.
这是一个想法,以(希望)有效的方式扩展IList .
public static IEnumerable <T> Shuffle <T>(此IList <T>列表)
{
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);
收益率表[choice [k]];
choices.RemoveAt(K);
}
收益率表[choice [0]];
}
您可以使用这种简单的扩展方法来实现
你可以通过以下方式使用它
如果你有一个固定的数字(75),你可以创建一个包含75个元素的数组,然后枚举你的列表,将元素移动到数组中的随机位置 . 您可以使用Fisher-Yates shuffle生成列表编号到数组索引的映射 .
我通常使用:
这是我首选的shuffle方法Fisher–Yates "inside-out" algorithm是Fisher–Yates "inside-out" algorithm的一个变体,适用于任何可枚举的序列(
source
的长度不需要从start开始知道) .该算法也可以通过分配从
0
到length - 1
的范围并通过将随机选择的索引与最后一个索引交换来随机耗尽索引来实现,直到所有索引都被恰好选择一次 . 上面的代码完成了完全相同的事情,但没有额外的分配 . 这很漂亮 .关于
Random
类,'s a general purpose number generator (and If I was running a lottery I'd考虑使用不同的东西) . 默认情况下,它还依赖于基于时间的种子值 . 问题的一个小缓解是使用RNGCryptoServiceProvider
播种Random
类,或者你可以在类似于此方法的方法中使用RNGCryptoServiceProvider
(见下文)来生成统一选择的随机双浮点值,但运行抽奖几乎需要了解随机性和随机源的本质 .生成随机双精度(仅在0和1之间)的点是用于缩放到整数解 . 如果你需要从一个列表中选择一个基于随机双
x
的东西,它总是0 <= x && x < 1
是直截了当的 .请享用!
如果您不介意使用两个
Lists
,那么这可能是最简单的方法,但可能不是最有效的或不可预知的一个:想法是通过项目和随机顺序获得无关的对象,然后按此顺序重新排序项目并返回值:
这是一个有效的Shuffler,它返回一个洗牌值的字节数组 . 它永远不会超过需要的洗牌 . 它可以从之前停止的地方重新启动 . 我的实际实现(未示出)是允许用户指定替换洗牌器的MEF组件 .
`
这是一种线程安全的方法:
对accepted answer进行简单修改,返回一个新列表而不是就地工作,并接受更一般的
IEnumerable<T>
,就像许多其他Linq方法一样 .老帖子肯定,但我只是使用GUID .
GUID始终是唯一的,因为每次结果每次更改时都会重新生成GUID .
解决此类问题的一种非常简单的方法是在列表中使用多个随机元素交换 .
在伪代码中,这看起来像这样: