Самый эффективный способ случайного "сортировки" (Shuffle) списка целых чисел в С#

Ответ 1

Хорошим алгоритмом перетасовки в режиме линейного времени является Fisher-Yates shuffle.

Одна из проблем, которые вы найдете в предложенном вами алгоритме, заключается в том, что, когда вы приближаетесь к концу перетасовки, ваш цикл будет тратить много времени на поиск случайно выбранных элементов, которые еще не были заменены. Это может занять неопределенный промежуток времени, как только он дойдет до последнего элемента для обмена.

Кроме того, похоже, что ваш алгоритм никогда не завершится, если есть нечетное число элементов для сортировки.

Ответ 2

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

Ответ 3

Мы можем сделать из этого метода расширения, чтобы получить случайный перечислитель для любого набора 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 в индексах списка, который мы хотим случайным образом перечислить. Его бит размером hog (выделение 4 * list.Count байтов), но работает в O (n).

Ответ 4

Как отметил Грег, лучший подход будет 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) предоставление достаточно случайный и непредвзятый Результаты

Ответ 5

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

Используя это, вам не нужно беспокоиться о промежуточной замене.

Ответ 6

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

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

Для размера данных, которые вы смотрите на него, не имеет большого значения.

Ответ 7

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

Ответ 8

Ответ 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;
    }

Обратите внимание, что в моих тестах этот алгоритм был в 6 раз медленнее, чем один ICR, однако это единственный способ получить нормальное распределение результатов

Ответ 9

Не было бы такого, как эта работа?

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

Ответ 10

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

 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;

        }
    }

Ответ 11

как насчет:

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

вуаля!

Ответ 12

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

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

Ответ 13

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