Нарисуйте n случайных элементов (без замены) из контейнера stl
Более или менее так же, как этот вопрос но где контейнер для выбора является как можно более общим (т. е. только Вперед контейнер или, может быть, даже просто Контейнер) в частицах не следует предполагать, что в контейнере есть .size (), и обходить его дважды (один раз для подсчета размера и еще раз для получения набора результатов) недопустимо.
У меня есть одно решение, которое немного сложнее и с несколькими зависимостями, чем хотелось бы, поэтому я надеюсь на что-то в диапазоне 3-5 строк.
Решение
Я предполагаю, что под «случайными элементами» вы подразумеваете элементы, распределенные равномерно.
Поскольку вы не знаете длины последовательности и не можете рассчитать ее заранее, вы должны постепенно строить свою случайную последовательность. Итак, давайте сделаем это, и надеемся, что все вероятности, которые мы используем, хорошо складываются, и мы в итоге получаем то, что хотели в первую очередь.
Мы сделаем это в два этапа. Сначала решите, какие из порядковых номеров нарисованы, а затем мы можем выбрать для них случайный порядок, если это необходимо (это не было ясно из вопроса). И я назову твой N ‘K’, потому что мне легче.
Сначала мы создаем массив элементов K, чтобы держать нарисованные элементы K. Мы просматриваем первые K элементов последовательности и копируем их в массив. Если последовательность не имеет K элементов, мы говорим «Нет, можно сделать».
Теперь мы знаем, что у нас есть K случайных элементов из последовательности размера K. Если мы находимся в конце последовательности, мы закончили. Если нет, мы знаем, что у нас есть последовательность размера K + 1. Здесь есть два варианта: либо выбран элемент K + 1, либо нет.
Какова вероятность выбора K + 1-го элемента? Мне легче вычислить вероятность того, что K + 1-й элемент не выбран. Существуют (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 не появляется в последовательности. Если случайное число больше этого, K + 1-й элемент появляется в последовательности. Выберите случайный элемент от 1 до K и замените его на K + 1-й элемент.
Теперь мы переходим к следующему пункту, К + 2-му пункту. И мы снова делаем то же самое. Вероятность того, что элемент K + 2 не появится в последовательности, равна (K + 1 над K) / (K + 2 над K).
Делайте это, пока последовательность не будет исчерпана. Затем у вас есть список из K элементов, случайно выбранных из последовательности.
Обратите внимание, что они не упорядочены случайным образом (по крайней мере, не для коротких последовательностей), поэтому вы можете выбрать для этого случайную перестановку K-размера.
Отказ от ответственности: вероятность — это сука, и, хотя мне это кажется правильным, есть вероятность, что я что-то пропустил, и конечный результат не будет распределен равномерно. Другие скажут довольно быстро.
Другие решения
Других решений пока нет …