Блог

У меня есть 7 элементов, k1-k7, и я хочу расположить их 30 различными способами, чтобы каждый элемент появлялся в каждой позиции с равной вероятностью.

 k1, k2, k3, k4, k5, k6, k7

k1, k4, k5, k3, k7, k6, k2

.

k6, k2, k7, k1, k5, k4, k3
  

Я не могу понять, какой метод для достижения этого. Пожалуйста, дайте мне знать, какой алгоритм будет работать здесь.

Если я вас правильно понимаю, то эти мысли должны сработать для вас:

Есть 7! = 5040 возможные способы упорядочить ваши элементы. Из этих 5040 уникальных последовательностей есть 6! = 720 такие, которые имеют k1 первую позицию, 720 имеют k2 первую позицию, …, 720 имеют k1 последнюю позицию, … и так далее. Итак, если вы случайным образом рисуете 30 из этих 5040 последовательностей, я думаю, результат должен соответствовать вашим требованиям.

Как их нарисовать? Ну, это зависит от используемого вами языка программирования. В C есть next_permutation . В Python есть itertools.permutations . Эти функции будут перебирать все 7! возможные расположения в лексикографическом порядке. Другие языки могут предлагать аналогичные инструменты.

Затем вы можете случайным образом сгенерировать число n в [0, ..., 5040[ и вызвать next_permutation n время в начальном диапазоне (или, в python, увеличить время итератора n ). Повторите это 30 раз. Однако обратите внимание, что для большего числа это может быстро стать очень неэффективным, не уверен, каковы ваши потребности в отношении эффективности.

Обновить

Чем больше я думаю о своем решении, тем больше я понимаю, что как их нарисовать? можно ответить намного лучше:

Все, что вам нужно, это единообразный алгоритм перетасовки. Это по определению будет равномерно генерировать одну из 7! перестановок, что в точности соответствует моему первоначальному ответу, но это будет намного эффективнее и намного проще в кодировании, поскольку большинство языков предоставляют такой алгоритм перетасовки (например, C ).

Я сохраню свой первоначальный ответ, потому что это помогает мне (и, надеюсь, другим) понять, почему равномерная перетасовка является правильным решением здесь.

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

Вы не можете, по крайней мере, не так, как указано в описании. Если k_1 должна была быть одинаковая вероятность появления в каждой позиции, то количество комбинаций, в которых он появился в позиции 1, было бы равно количеству комбинаций, в которых он появился в каждой из других позиций. Но это означает, что количество комбинаций должно быть кратно 7, а 30 — нет.

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