Cách hiệu quả nhất để ngẫu nhiên "sắp xếp" (Trộn) một danh sách các số nguyên trong C#

Question

Tôi cần phải sắp xếp ngẫu nhiên một danh sách các số nguyên (0-1999) theo cách hiệu quả nhất có thể. Bất kỳ ý tưởng?

Hiện nay, tôi đang làm một cái gì đó như thế này:

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

Một tốt tuyến tính thời gian xáo trộn thuật toán là Fisher-Yates shuffle.

Một vấn đề bạn sẽ tìm thấy với thuật toán được đề xuất của bạn là khi bạn gần cuối shuffle, vòng lặp của bạn sẽ dành nhiều thời gian tìm kiếm các yếu tố được chọn ngẫu nhiên chưa được đổi chỗ. Điều này có thể mất một lượng thời gian không xác định khi nó được chuyển đến phần tử cuối cùng để hoán đổi.

Ngoài ra, có vẻ như thuật toán của bạn sẽ không bao giờ chấm dứt nếu có một số phần tử lẻ cần sắp xếp.

Answer 2

Để cải thiện hiệu quả của bạn, bạn có thể giữ một tập hợp các giá trị/chỉ mục đã được hoán đổi thay vì boolean cho biết chúng đã được hoán đổi. Chọn chỉ số hoán đổi ngẫu nhiên của bạn từ nhóm còn lại. Khi hồ bơi là 0, hoặc khi bạn thực hiện nó thông qua danh sách ban đầu thì bạn đã hoàn tất. Bạn không có khả năng cố gắng chọn giá trị chỉ số trao đổi ngẫu nhiên.

Khi bạn thực hiện trao đổi, chỉ cần xóa chúng khỏi hồ bơi.

Đối với kích thước dữ liệu bạn đang xem, không phải là vấn đề lớn.

Answer 3

Tôi không chắc chắn của các yếu tố hiệu quả, nhưng tôi đã sử dụng một cái gì đó tương tự như sau, nếu bạn không phản đối việc sử dụng một 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; 
} 

Sử dụng này, bạn không cần phải lo lắng về việc hoán đổi trung gian.

Answer 4

Vì Greg đã chỉ ra Fisher-Yates shuffle sẽ là phương pháp tốt nhất. Đây là một thực hiện các thuật toán từ Wikipedia:

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

Việc thực hiện trên dựa vào Random.nextInt (int) cung cấp đủ ngẫu nhiên và không thiên vị kết quả

Answer 5

Sẽ không phải cái gì đó như công việc này?

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

sửa đổi để xử lý danh sách hoặc các đối tượng khác thực hiện IEnumerable

Answer 7

Chúng ta có thể thực hiện một phương pháp mở rộng ra những điều này để có được một Enumerator ngẫu nhiên cho bất kỳ bộ sưu tập 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]; 
     } 
    } 
} 

sử dụng này Đảo ngược Fisher-Yates xáo trộn các chỉ mục của danh sách mà chúng ta muốn ngẫu nhiên liệt kê. Của nó một chút của một kích thước hog (phân bổ 4 * list.Count byte), nhưng chạy trong O (n).

Answer 8

Tôi đã thực hiện một phương pháp sử dụng một Hashtable tạm thời, cho phép sắp xếp khóa tự nhiên của Hashtable để phân ngẫu nhiên. Đơn giản chỉ cần thêm, đọc và loại bỏ.

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

Tôi đoán hai dòng cuối cùng phải được hoán đổi trong câu trả lời của Micah. Vì vậy, các mã có thể trông như

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

câu trả lời ICR là rất nhanh, nhưng các mảng kết quả không được phân phối bình thường. Nếu bạn muốn có một phân phối chuẩn, đây là các mã:

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

Lưu ý rằng trong các thử nghiệm của tôi, thuật toán này là chậm hơn so với một ICR cung cấp 6 lần, tuy nhiên điều này là cách duy nhất tôi có thể đưa ra để có được một phân phối kết quả bình thường

Answer 12

gì về:

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

thì đấy!