Самый эффективный способ случайной «сортировки» (перемешивания) списка целых чисел в 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

Хорошим алгоритмом тасования по линейному времени является тасовка Фишера-Йейтса .

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

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

Answer 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

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

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

Answer 4

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

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

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

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

Answer 7

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

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

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

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

Answer 9

а как же:

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

вуаля!

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

        }
    }