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

瞧！