Отчет по производственной практике, научно-исследовательской работе
Алгебраические комбинаторные размещения
жүктеу/скачать 177 Kb.
|
2.1.2. Алгебраические комбинаторные размещенияПусть задано некоторое конечное множество из N различных элементов. И требуется выбрать из него M элементов. Выбранные M из предложенных N элементов называются выборкой. Если важен порядок, в котором произведена выборка элементов, то говорят об упорядоченной выборке, если порядок не важен, то говорят о неупорядоченной выборке. В комбинаторике упорядоченная выборка объемом M элементов из предложенного множества N различных элементов называется размещением из N элементов по M. Все комбинации внутри размещения могут отличаться друг от друга как самими элементами, так и порядком их расположения. Различают также размещения без повторений (когда все M элементов внутри выборки различны) и размещения с повторениями. В случае размещения без повторений количество элементов множества N≥M. Количество размещений без повторений для N различных элементов по M составляет составляет: В случае если N=M, количество размещений совпадает с количеством перестановок без повторений и составляет N!. Такое же количество размещений получится в случае если M=N-1. Рассмотрим задачу получения всех размещений без повторений для чисел 1…N по M. Для генерации всех возможных размещений из N по M в лексикографическом порядке воспользуемся ранее рассмотренным решением для генерации перестановок без повторений. Размещения с повторениями В случае если элементы из множества N могут повторяться в выборках по M элементов, общее количество таких размещений составляет При этом не накладывается ограничений на размерность рассматриваемого массива N по сравнению с M (может быть как N≥M, так и N |