Отчет по производственной практике, научно-исследовательской работе


Алгебраические комбинаторные перестановки



бет6/10
Дата31.05.2023
өлшемі177 Kb.
#474529
түріОтчет
1   2   3   4   5   6   7   8   9   10
НИР Конюхов

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).

  2. Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.

  3. Поменять местами два полученных элемента.

  4. Теперь в части массива, которая размещена справа от позиции 1 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть.

  5. Таким образом мы получим новую последовательность, которая будет рассматриваться в качестве исходной на следующем шаге.

Перестановки с повторениями


Особого внимания заслуживает задача генерации перестановок 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.






Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   10




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет