随机化一个整数数组
本文关键字:一个 整数 数组 随机化 | 更新日期: 2023-09-27 18:13:02
你能帮我找到一种随机化数组的方法吗?例如:
int[] arrayInt = { 1, 2, 3, 4, 5, 6, 7 };
随机化后,结果应存储在另一个数组中。
当你再次随机化时,它应该与存储在第二个数组中的值进行比较,如果该值存在,程序必须再次随机化。
下面是使用Enumerable.OrderBy
对带有随机变量的输入数组排序的方法。生成新序列后,将用SequenceEqual
与输入数组进行比较:
public static T[] UniqueRandomArray<T>(T[] input, Random rnd)
{
if (input.Length <= 1) throw new ArgumentException("Input array must have at least two elements, otherwise the output would be the same.", "input");
IEnumerable<T> rndSeq;
while (input.SequenceEqual(rndSeq = input.OrderBy(x => rnd.Next())));
return rndSeq.ToArray();
}
这个示例代码生成10个新数组,它们被添加到List中。确保新数组与前一个数组不同:
Random rnd = new Random();
List<int[]> randomArrays = new List<int[]>();
int[] arrayInt1 = { 1, 2, 3, 4, 5, 6, 7 };
randomArrays.Add(arrayInt1);
for (int i = 0; i < 10; i++)
{
int[] lastArray = randomArrays[randomArrays.Count - 1];
int[] randomArray = UniqueRandomArray(lastArray, rnd);
randomArrays.Add(randomArray);
}
using linq
Random rand = new Random();
int[] arrayInt =
new[] {1, 2, 3, 4, 5, 6, 7}.Select(x => new {x, r = rand.Next()})
.OrderBy(x => x.r)
.Select(x => x.x)
.ToArray();
你可以随机选择任意类型
public static class RandomExt
{
public static T[] RandomizeOrder<T>(this T[] array)
{
var rand = new Random();
return array.Select(x => new {x, r = rand.Next()})
.OrderBy(x => x.r)
.Select(x => x.x)
.ToArray();
}
}
int[] arrayInt = new[] {1, 2, 3, 4, 5, 6, 7}.RandomizeOrder();
你问题的第一部分是关于数组的洗牌。一个很好的算法是Fisher-Yates shuffle。
关于将结果与原始结果进行比较的下一部分有点模糊。我假设您希望创建一个随机洗牌,以确保所有元素都洗牌到一个新位置。例如
- [0,1,2] =>[1,2,0]是可以的,但是
- [0, 1, 2] =>[2, 1, 0]不可以,因为1在原地不动
我已经为此创建了一些扩展(请注意,这是一个元素类型为T
的通用解决方案):
static class EnumerableExtensions {
static Random random = new Random();
public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source) {
var list = source.ToList();
for (var k = 0; k < list.Count; k += 1) {
var j = random.Next(k, list.Count);
Swap(list, k, j);
}
return list;
}
public static IEnumerable<T> RandomizeUniquely<T>(this IEnumerable<T> source) {
while (true) {
var randomized = source.Randomize();
var isNotUnique = source
.Zip(randomized, (a, b) => Equals(a, b))
.Any(equal => equal);
if (!isNotUnique)
return randomized;
}
}
static void Swap<T>(IList<T> list, Int32 i, Int32 j) {
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
Randomize
方法实现Fisher-Yates洗牌。RandomizeUniquely
使用此方法并尝试创建满足上述条件的洗牌。该方法只是简单地尝试,直到找到满意的洗牌。请注意,此算法可能不会终止。例如,如果源只有一个元素,则找不到唯一的shuffle。此外,如果源包含重复项,则解决方案可能不存在。
要使用该方法,只需像这样调用:
var randomized = Enumerable.Range(1, 7).RandomizeUniquely();
可以通过验证参数和决定如何处理上面描述的不终止问题来改进代码。
希望这对你有帮助。使用一个安全的加密提供程序和一个安全的哈希值来进行比较——过度了,所以可以随意调整使用的提供程序:)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.Collections;
using System.Collections.Concurrent;
namespace RandomiseArray
{
static class Program
{
static void Main(string[] args)
{
// source array
string[] s = new string[] { "a", "b", "c", "d", "e", "f", "g" };
// number of unique random combinations required
int combinationsRequired = 5;
var randomCombinations = s.Randomise(System.Text.UnicodeEncoding.Unicode.GetBytes, combinationsRequired);
foreach (var c in randomCombinations)
Console.WriteLine(c.Aggregate((x, y) => x + "," + y));
Console.ReadLine();
}
/// <summary>
/// given a source array and a function to convert any item in the source array to a byte array, produce x unique random sequences
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="source"></param>
/// <param name="byteFunction"></param>
/// <param name="x"></param>
/// <returns></returns>
public static IEnumerable<IEnumerable<T>> Randomise<T>(this IEnumerable<T> source, Func<T, byte[]> byteFunction, int x)
{
var foundValues = new ConcurrentDictionary<byte[], T[]>();
int found = 0;
do
{
T[] y = source.Randomise().ToArray();
var h = y.Hash(byteFunction);
if (!foundValues.Keys.Contains(h))
{
found++;
foundValues[h] = y;
yield return y; // guaranteed unique combination (well, within the collision scope of SHA512...)
}
} while (found < x);
}
public static IEnumerable<T> Randomise<T>(this IEnumerable<T> source)
{
using (RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider())
return source.OrderBy(i => rng.Next());
}
public static int Next(this RNGCryptoServiceProvider rng)
{
byte[] buf = new byte[4];
rng.GetBytes(buf);
return BitConverter.ToInt32(buf, 0);
}
public static byte[] Hash<T>(this IEnumerable<T> items, Func<T, byte[]> getItemBytes)
{
using (SHA512CryptoServiceProvider sha = new SHA512CryptoServiceProvider())
return sha.ComputeHash(items.SelectMany(i => getItemBytes(i)).ToArray());
}
}
}
OrderBy是一种很好的洗牌方式,但它使用的排序是O(n log n).洗牌可以在O(n)内完成。
这是来自维基百科的伪代码
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]