Отчет по производственной практике, научно-исследовательской работе
Алгебраические комбинаторные перестановки
жүктеу/скачать 177 Kb.
|
2.1.1. Алгебраические комбинаторные перестановкиПерестановка – это комбинация элементов из N разных элементов, взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов. Перестановки без повторений Количество перестановок для N различных элементов составляет N!. Действительно: На первое место может быть помещен любой из N элементов (всего вариантов N), а вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1)), если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1, то есть всего N! перестановок. Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N, а последней — N N-1 … 1. Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги: Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1). Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге. Поменять местами два полученных элемента. Теперь в части массива, которая размещена справа от позиции 1 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть. Таким образом мы получим новую последовательность, которая будет рассматриваться в качестве исходной на следующем шаге. Перестановки с повторениями Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n1, n2... nk, где элемент n1 повторяется r1 раз, n2 повторяется r2 раз и т.д. При этом n1+n2+...+nk=N. Если мы будем считать все n1+n2+...+nk элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n1+n2+...+nk)! . Однако среди этих перестановок не все различны. В самом деле, все r1 элементов n1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n2, n3 и т. д. В итоге имеем r1! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n1. Таким образом, всякая перестановка может быть записана r1!·r2!·...·rk! способами. Следовательно, число различных перестановок с повторениями равно Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Код программы и результат ее выполнения прикреплен в Приложении 1. жүктеу/скачать 177 Kb. Достарыңызбен бөлісу:
|