Алгоритм случайного воспроизведения - PullRequest
Новая
       20

Алгоритм случайного воспроизведения

13 голосов
/ 29 ноября 2009

Мне нужно создать список чисел из диапазона (например, от x до y) в случайном порядке, чтобы каждый ордер имел равные шансы.

Мне это нужно для музыкального проигрывателя, который я пишу на C #, для создания списков воспроизведения в случайном порядке.

Есть идеи?

Спасибо.

РЕДАКТИРОВАТЬ: Меня не интересует изменение исходного списка, просто подберите случайные индексы из диапазона в случайном порядке, чтобы у каждого заказа был равный шанс.

Вот что я написал до сих пор: 

    public static IEnumerable<int> RandomIndexes(int count)
    {
        if (count > 0)
        {
            int[] indexes = new int[count];
            int indexesCountMinus1 = count - 1;

            for (int i = 0; i < count; i++)
            {
                indexes[i] = i;
            }

            Random random = new Random();

            while (indexesCountMinus1 > 0)
            {
                int currIndex = random.Next(0, indexesCountMinus1 + 1);
                yield return indexes[currIndex];

                indexes[currIndex] = indexes[indexesCountMinus1];
                indexesCountMinus1--;
            }

            yield return indexes[0];
        }
    }

Это работает, но единственная проблема в том, что мне нужно выделить массив в памяти размером count. Я ищу то, что доза не требует выделения памяти.

Спасибо.

Ответы [ 12 ]

0 голосов
/ 02 декабря 2009

С логической точки зрения это возможно. Учитывая список n песен, существует n! перестановок; если вы присваиваете каждой перестановке число от 1 до n! (или от 0 до n! -1 :-D) и выбираете одно из этих чисел случайным образом, вы можете сохранить номер перестановки, которую вы используете в данный момент, вместе с исходным списком и индексом текущей песни внутри перестановки.

Например, если у вас есть список песен {1, 2, 3}, ваши перестановки: 

0: {1, 2, 3}
1: {1, 3, 2}
2: {2, 1, 3}
3: {2, 3, 1}
4: {3, 1, 2}
5: {3, 2, 1}

Таким образом, единственные данные, которые мне нужно отслеживать, - это исходный список ({1, 2, 3}), индекс текущей песни (например, 1) и индекс перестановки (например, 3). Затем, если я хочу найти следующую песню для воспроизведения, я знаю, что это третья (2, но с нуля) песня перестановки 3, например, Песня 1.

Однако этот метод основан на том, что у вас есть эффективные средства для определения i -ой песни из j -ой перестановки, о которой, пока у меня не было возможности подумать с более сильным математическим фоном, чем я могу вставить) эквивалентно «тогда происходит чудо». Но принцип есть.

0 голосов
/ 02 декабря 2009

Вы можете использовать трюк, который мы делаем на сервере SQL, чтобы упорядочивать наборы случайным образом, как это с использованием guid. значения всегда распределяются одинаково случайным образом. 

private IEnumerable<int> RandomIndexes(int startIndexInclusive, int endIndexInclusive)
{
    if (endIndexInclusive < startIndexInclusive)
        throw new Exception("endIndex must be equal or higher than startIndex");

    List<int> originalList = new List<int>(endIndexInclusive - startIndexInclusive);
    for (int i = startIndexInclusive; i <= endIndexInclusive; i++)
        originalList.Add(i);

    return from i in originalList
           orderby Guid.NewGuid()
           select i;
}
Страница:
...