Последний пост в блоге

Полезные штуки: Random 20 Apr 2010 11:28

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

Задача: есть некоторая последовательность объектов. Возможно, неизвестной длины. Надо выбрать случайный элемент этой последовательности, так чтобы вероятность выбора любого конкретного была одинакова. Вариант "со звездочкой" — для каждого элемента последовательности задан вес, надо чтобы вероятность выбора элемента была пропорциональна весу.

Обычно это решается просто: элемент номер n, где n — случайное число от 0 до N, а N — длина последовательности. Ну, типа,

return sequence[random.Next(0, sequence.Count)];

Но для этого надо знать число элементов. И иметь доступ по индексу тоже неплохо бы. А если последовательность, как в нашем условии, этого не имеет? В терминах C# — это IEnumerable. Есть способ решения и в этом случае.

Работая с IEnumerable, все что мы можем — это перебирать элементы последовательно. Подойдем к вопросу так: пусть мы, перебирая последовательность, выбрали некий элемент Х из первых n. Теперь мы берем следующий элемент, номер n+1. C какой вероятностью мы выберем именно его? Если последовательность заканчивается на нем, ответ очевиден: $1/(n+1)$. Менее очевидно, что с той же вероятностью его надо выбирать и в остальных случаях! Попробуем посчитать вероятность для случая, когда длина последовательности n+2:

  • на шаге n+1 мы выберем наш элемент с вероятностью $1/(n+1)$
  • на шаге n+2 мы выберем _следующий_ элемент с вероятностью $1/(n+2)$; а предыдущий останется выбран с вероятностью $\frac{n+1}{n+2}$
  • в итоге, элемент с номером n+1 окажется выбранным с вероятностью $\frac{1}{n+1} \frac{n+1}{n+2} = \frac{1}{n+2}$ — что и требовалось!

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

Итого, алгоритм выбора случайного элемента простой: перебираем последовательно элементы, на каждом шаге с вероятностью 1/(число шагов) отмечаем текущий элемент как выбранный. Последний выбранный и возвращаем.

Подобную штуку так и хочется написать в виде метода расширения, чтоб потом использовать с любыми последовательностями не задумываясь1 . Так и сделаем.

    public static class RandomSelectExtension
    {
        public static T Random<T>(this IEnumerable<T> enumerable, Random rng)
        {
            int totalCount = 0; // число шагов
            T selected = default(T); // последний выбранный элемент
            foreach (var data in enumerable) // перебираем элементы
            {
                int r = rng.Next(totalCount+1); // случайное число от 0 до totalCount включительно 
                if (r >= totalCount) // с вероятностью 1/(totalCount+1)
                    selected = data; // выбираем текущий элемент
                totalCount++; // и следующий шаг
            }
 
            return selected;
        }
    }

Генератор случайных чисел передадим в метод на всякий случай — можно было бы каждый раз создавать новый, но это во-первых неэффективно, а во-вторых, может быть, пользователь захочет управлять seed-ом.

Ну и наконец, к вопросу о задаче со звездочкой. Как быть, если веса элементов разные? Как оказалось, точно так же - только вместо номера шага надо брать вес элемента. То есть, если вес i-того элемента wi, то элемент номер n+1 выбирается с вероятностью $\frac{w_{n+1}}{\sum_{i=1}^{n}w_i}$. Доказывается это абсолютно так же, как и для случая равных весов — суммы опять сократятся. А реализуется, например, так:

    public static class RandomSelectExtension
    {
        public static T Random<T>(this IEnumerable<T> enumerable, Random rng, Func<T, int> weightFunc)
        {
            int totalCount = 0; // теперь это - суммарный вес всех предыдущих элементов
            T selected = default(T);
            foreach (var data in enumerable)
            {
                int r = rng.Next(totalCount + weightFunc(data)); // weightFunc вычисляет вес текущего элемента
                if (r >= totalCount)
                    selected = data;
                totalCount += weightFunc(data);
            }
 
            return selected;
        }
    }

Здесь мы передали в метод функцию, которая вычисляет вес по конкретному элементу. В конкретном приложении это будет использоваться примерно так:

return list.Random(m_Random, pd => pd.Count);

То есть, вес это поле класса, экземпляры которого лежат в списке.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License