在C＃中随机“整理”（整理）整数列表的最有效方法

Question

我需要以最有效的方式随机“整理”整数列表（0-1999）。有任何想法吗？

目前，我做这样的事情：

bool[] bIndexSet = new bool[iItemCount]; 

for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++) 
{ 
    int iSwapIndex = random.Next(iItemCount); 
    if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex) 
    { 
     int iTemp = values[iSwapIndex]; 
     values[iSwapIndex] = values[iCurIndex]; 
     values[iCurIndex] = values[iSwapIndex]; 
     bIndexSet[iCurIndex] = true; 
     bIndexSet[iSwapIndex] = true; 
    } 
} 

Answer 1

良好的线性时间的洗牌算法是Fisher-Yates shuffle。

您提出的算法会遇到的一个问题是，当您接近洗牌结束时，您的循环将花费大量时间寻找尚未交换的随机选择的元素。一旦到达交换的最后一个元素，这可能需要一段不确定的时间。

另外，它看起来像你的算法将永远不会终止，如果有奇数个元素进行排序。

Answer 2

为了提高效率，您可以保留一组已被交换的值/索引，而不是用于指示它们已交换的布尔值。从剩余池中挑选随机交换索引。当池为0时，或者当您通过初始列表完成后，就完成了。您无法尝试选择随机交换索引值。

当您进行交换时，只需从池中删除它们即可。

对于您正在查看的数据大小而言，没有什么大不了的。

Answer 3

我不知道效率的因素，但我已经使用类似如下的东西，如果你不反对使用一个ArrayList：

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

用这种方法，你不必担心关于中间交换。

Answer 4

Greg指出Fisher-Yates shuffle是最好的方法。下面是来自维基百科的算法的实现：提供 足够的随机性和不带偏见 结果

public static void shuffle (int[] array) 
{ 
    Random rng = new Random(); // i.e., java.util.Random. 
    int n = array.length;  // The number of items left to shuffle (loop invariant). 
    while (n > 1) 
    { 
     int k = rng.nextInt(n); // 0 <= k < n. 
     n--;      // n is now the last pertinent index; 
     int temp = array[n];  // swap array[n] with array[k] (does nothing if k == n). 
     array[n] = array[k]; 
     array[k] = temp; 
    } 
} 

上面的实现依赖于 Random.nextInt（INT）

Answer 5

岂不像这项工作？

var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; 
var random = new Random(); 
list.Sort((a,b)=>random.Next(-1,1)); 

Answer 6

static Random random = new Random(); 

public static IEnumerable<T> RandomPermutation<T>(IEnumerable<T> sequence) 
{ 
    T[] retArray = sequence.ToArray(); 


    for (int i = 0; i < retArray.Length - 1; i += 1) 
    { 
     int swapIndex = random.Next(i, retArray.Length); 
     if (swapIndex != i) { 
      T temp = retArray[i]; 
      retArray[i] = retArray[swapIndex]; 
      retArray[swapIndex] = temp; 
     } 
    } 

    return retArray; 
} 

修改，以处理列表或其他对象实现IEnumerable的

Answer 7

我们可以扩展方法出这得到一个随机枚举任何的IList集合

class Program 
{ 
    static void Main(string[] args) 
    { 
     IList<int> l = new List<int>(); 
     l.Add(7); 
     l.Add(11); 
     l.Add(13); 
     l.Add(17); 

     foreach (var i in l.AsRandom()) 
      Console.WriteLine(i); 

     Console.ReadLine(); 
    } 
} 


public static class MyExtensions 
{ 
    public static IEnumerable<T> AsRandom<T>(this IList<T> list) 
    { 
     int[] indexes = Enumerable.Range(0, list.Count).ToArray(); 
     Random generator = new Random(); 

     for (int i = 0; i < list.Count; ++i) 
     { 
      int position = generator.Next(i, list.Count); 

      yield return list[indexes[position]]; 

      indexes[position] = indexes[i]; 
     } 
    } 
} 

此用途对我们想要随机列举的列表的索引进行反向Fisher-Yates混洗。它有点大小（分配4 * list.Count字节），但在O（n）中运行。

Answer 8

我做了一个使用临时Hashtable的方法，允许Hashtable的自然键排序随机化。只需添加，阅读和放弃。

int min = 1; 
int max = 100; 
Random random; 
Hashtable hash = new Hashtable(); 
for (int x = min; x <= max; x++) 
{ 
    random = new Random(DateTime.Now.Millisecond + x); 
    hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x); 
} 
foreach (int key in hash.Keys) 
{ 
    HttpContext.Current.Response.Write("<br/>" + hash[key] + "::" + key); 
} 
hash.Clear(); // cleanup 

Answer 9

我想最后两行必须在Micah的答案中互换。因此，代码可能看起来像

public static void shuffle(int[] array) { 
     Random rng = new Random(); // i.e., java.util.Random. 
     int n = array.Length;  // The number of items left to shuffle (loop invariant). 
     while (n > 1) { 
      int k = rng.Next(n); // 0 <= k < n. 
      n--;      // n is now the last pertinent index; 
      int temp = array[n];  // swap array[n] with array[k] (does nothing if k == n). 
      array[n] = array[k]; 
      array[k] = temp; 

     } 
    } 

Answer 10

itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList() 

Answer 11

ICR的回答是非常快的，但由此产生的阵列不是正态分布。如果你想有一个正态分布，下面的代码：

public static IEnumerable<T> RandomPermutation<T>(this IEnumerable<T> sequence, int start,int end) 
    { 
     T[] array = sequence as T[] ?? sequence.ToArray(); 

     var result = new T[array.Length]; 

     for (int i = 0; i < start; i++) 
     { 
      result[i] = array[i]; 
     } 
     for (int i = end; i < array.Length; i++) 
     { 
      result[i] = array[i]; 
     } 

     var sortArray=new List<KeyValuePair<double,T>>(array.Length-start-(array.Length-end)); 
     lock (random) 
     { 
      for (int i = start; i < end; i++) 
      { 
       sortArray.Add(new KeyValuePair<double, T>(random.NextDouble(), array[i])); 
      } 
     } 

     sortArray.Sort((i,j)=>i.Key.CompareTo(j.Key)); 

     for (int i = start; i < end; i++) 
     { 
      result[i] = sortArray[i - start].Value; 
     } 

     return result; 
    } 

注意，在我的测试中，该算法是随机提供的ICR慢6倍，但是这是我能想出获得的唯一途径正常结果分布

Answer 12

怎么样：

System.Array.Sort(arrayinstance, RandomizerMethod); 
... 
//any evoluated random class could do it ! 
private static readonly System.Random Randomizer = new System.Random(); 

private static int RandomizerMethod<T>(T x, T y) 
    where T : IComparable<T> 
{ 
    if (x.CompareTo(y) == 0) 
     return 0; 

    return Randomizer.Next().CompareTo(Randomizer.Next()); 
} 

瞧！