Как расставить k предметов по N путям с равной вероятностью

Question

У меня есть 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

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

Answer 1

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

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

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

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

Обновление

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

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

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

Answer 2

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

Answer 3

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

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