Самый эффективный способ случайным образом “отсортировать” (Перестановка) список целых чисел в C#

Вот то, что я использовал. Это - конечно, не самое быстрое, но это, вероятно, достаточно хорошо для большинства случаев и самое главное, это очень просто.

IEnumerable<ListItem> list = ...;
Random random = new Random(); // important to not initialize a new random in the OrderBy() function
return list.OrderBy(i => random.Next());

Я создал метод, использующий временную 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

Я полагаю, что в ответе Михи последние две строки нужно поменять местами. Итак, код может выглядеть так

 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;

        }
    }

Мы можем сделать дополнительный метод из этого для получения Случайного перечислителя для любого набора 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];
        }
    }
}   

, Это использует обратного Фишера-Йетса, надевают индексы списка, который мы хотим случайным образом перечислить через. Это - что-то вроде пожирателя ресурсов размера (выделяющий 4*list. Байты количества), но выполнения в O (n).

Как Greg указал , перестановка Фишера-Йетса будет лучшим подходом. Вот реализация алгоритма из Википедии:

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 (интервал), обеспечивающий достаточно случайные и несмещенные результаты

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

Для повышения эффективности, можно сохранить ряд значений/индексов, которые были подкачаны, а не булевская переменная для указания, что они были подкачаны. Выберите свой рандомизированный индекс подкачки от остающегося пула. Когда пул 0, или когда Вы сделали его через первоначальный список затем, Вы сделаны. У Вас нет потенциала, чтобы попытаться выбрать случайное индексное значение подкачки.

, Когда Вы сделаете подкачку, просто удалите их из пула.

Для размера данных Вы смотрите на него, не никакое грандиозное предприятие.

Я не уверен в коэффициенте полезного действия, но я использовал что-то подобное следующему, если Вы не настроены против использования 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;
}

Используя это, Вы не должны волноваться о промежуточном свопинге.

Разве что-то вроде этого не работало бы?

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