Нарисуйте n случайных элементов (без замены) из контейнера stl

Question

Более или менее то же, что и this question, но где выбранный контейнер является максимально общим (т.е. только Forward Container или, может быть, просто простым Container) в частицы не следует предполагать, что контейнер имеет .size() и проходит его дважды (один раз для подсчета размера и снова для получения набора результатов) неприемлемо.

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

Answer 1

Я предполагаю, что «случайные элементы» означает элементы, распределенные равномерно.

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

Мы сделаем это в два этапа. Сначала определите, какой из порядковых номеров нарисован, и тогда мы можем выбрать для них случайный порядок, если нам нужно (это было непонятно из вопроса). И я позвоню вашему N'K, потому что мне легче.

Сначала мы создаем массив элементов K, чтобы удерживать K рисованных элементов. Перейдем к первым K элементам последовательности и скопируем их в массив. Если в последовательности нет K-элементов, мы говорим: «Нет, может сделать».

Теперь мы знаем, что у нас есть K случайных элементов из последовательности K-размера. Если мы находимся в конце последовательности, мы закончили. Если нет, мы знаем, что у нас есть последовательность размера K + 1. Здесь есть два варианта: выбирается либо K + 1'th элемент, либо нет.

Какова вероятность выбора элемента K + 1'th? Мне легче рассчитать вероятность того, что K + 1'th элемент равен , а не. Существуют (K + 1 над K) способы выбора K элементов из K + 1 и только (K над K) способами выбора K элементов, если элемент K + 1 не появляется. Итак, (K над K)/(K + 1 над K) - вероятность того, что K + 1'-й элемент не будет выбран.

Итак, выберите случайное число между 0 и 1, если оно меньше 1/(K + 1), элемент K + 1'th не появляется в последовательности. Если случайное число больше, то в последовательности появляется K + 1'-й элемент. Выберите случайный элемент между 1 и K и замените его на элемент K + 1'th.

Теперь мы переходим к следующему элементу, K + 2'th item. И мы делаем то же самое снова. Вероятность появления K + 2-го элемента в последовательности (K + 1 над K)/(K + 2 над K).

Сделайте это до тех пор, пока последовательность не будет исчерпана. Затем у вас есть список K элементов, случайно выбранных из последовательности.

Обратите внимание, что они не упорядочены случайным образом (по крайней мере, не для коротких последовательностей), поэтому вы можете выбрать для них случайную перестановку K-размера.

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