Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рекурсивный алгоритм генерирования всех перестановок заданного множества в лексикографическом порядке

Введение

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

1. Постановка задачи

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

Устройствами ввода информации являются клавиатура и мышь.

Программа должна быть разработана для работы в операционной системе Microsoft Windows.

2. Теоретическая часть

Рассмотрим рекурсивный алгоритм генерирования перестановок в лексикографическом порядке. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения: в первой перестановке элементы идут в растущей последовательности, а в последней - в убывающей другими словами последняя перестановка является обращением первой, последовательность всех перестановок можно разделить на n блоков длины (n-1), соответствующих возрастающим значениям элемента в первой позиции. Последние n-1 позиций блока, содержащего элемент р в первой позиции, определяют последовательность перестановок множества {1,2,…, n}\{р} в лексикографическом порядке.

В качестве примера рассмотрим генерирование всех перестановок для п=4. Таких перестановок будет 4!=24. Эти перестановки можно разбить на четыре блока, каждый из которых содержит 3!=6 перестановок, по значению элемента в первой позиции. В первом блоке на первом месте стоит 1, во втором - 2, в третьем - 3, в четвертом - 4. Далее рассмотрим блок с 1 на первом месте, для остальных аналогично. Для генерации всех перестановок оставшегося множества Х={1,2,3} выполним следующее: разобьем все перестановки на 3 блока по 2!=2 перестановки, соответствующих возрастающим значениям элемента в первой позиции, в первом блоке - 1, во втором - 2, в третьем - 3. Далее в каждом блоке генерируем все перестановки из оставшихся двух элементов в лексикографическом порядке (в первой из перестановок последние два элемента расположены в порядке возрастания).

3. Описание программы

Для написания данной программы использовался язык программирования Python. Язык Python является одним из самых популярных языков программирования. Python был выбран в качестве основного языка для решения поставленной задачи из-за ряда свойств:

1. Некоторые языковые конструкции позволяют в одну строчку кода уместить решение сложных задач;

2. Программы могут запускаться на любой платформе, на которой есть интерпретатор Python.

3. Стандартная библиотека языка содержит готовые решения для большинства задач, от написания ультилит до создания WEB-приложений.

4. Даже если стандартной библиотеки будет не достаточно, то можно легко установить стороннюю библиотеку при помощи консольной команды pip install.

Исходя из этого, решать сложные задачи на этом языке удается очень легко и быстро.

Например, необходимо перевести число в двоичную систему счисления из любой другой и сосчитать количество единиц в этом числе. Решение задачи и пример работы представлен на рисунке 3.1

Рисунок 3.1. Пример кода на Python

В качестве среды программирования был выбран программный продукт от компании JetBrains Pycharm.

Для создания графического интерфейса использовался пакет PyQt 5.

Интерфейс очень прост и состоит из не большего числа элементов, это кнопка запуска работы алгоритма, spin-box для задания длины последовательности и зона вывода информации. На рисунке 3.2 представлено диалоговое окно программы.

Рисунок 3.2. Окно программы

Для запуска программы нужно выбрать длину последовательности и нажать кнопку «Генерировать». Получив необходимое число, начинается генерация последовательности до этого числа, и алгоритм начинает работу. В качестве результата возвращается список всех возможных перестановок заданного множества, который выводится на экран.

Блок-схема программы представлена на рисунке 3.3. Перед запуском основной функции генерации перестановок, инициализируются массивы в глобальной области видимости, которые будут хранить информацию о перестановках. Массив «Б» хранит метки, массив «А» хранит очередную перестановку. Блок схема алгоритма генерации перестановок представлен на рисунке 3.4.

Рисунок 3.3. Схема работы программы

Рисунок 3.4. Схема работы алгоритма генерации перестановок

4. Отладка и тестирование

В качестве среды разработки была выбрана программа Pycharm 2017.1 которая содержит в себе все необходимые средства для разработки и отладки модулей и программ. Для отладки программы использовались различные инструменты: точка остановки, пошаговое выполнение кода программы, анализ содержимого глобальных и локальных переменных.

Тестирование проводилось в рабочем порядке, в процессе разработки и после завершения написания программы.

В ходе отладки программы выяснилось, что при увеличении длины заданной последовательности, уменьшается скорость выполнения программы. Это вызвано тем, что оценочная сложность алгоритма О (n!), где n - длина последовательности. Так же при задании очень длиной последовательности фиксировалось исключение RecursionError, которое представлено на рисунке 4.1.

Рисунок 4.1. Исключение RecursionError

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

На рисунке 4.2 представлены результаты работы программы при малой длине последовательности, так как при большой длине на одной картинке трудно показать все перестановки.

Рисунок 4.2. Результат работы программы

Заключение

При выполнении данной курсовой работы были получены навыки программирования на языке Python и создания графических интерфейсов программ, усовершенствованы навыки разработки многомодульных программ. Изучены основные возможности среды программирования Pycharm 2017.1, получены навыки отладки и тестирования программ. Были рассмотрены некоторые функции из стандартной библиотеки языка Python.

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

Список используемых источников

программа алгоритм лексикографический множество

1. М. Лутц - «Программирование на Python»

2. В. Дронов, Н. Прохоренко - «Python 3 и PyQt 5. Разработка приложений»

3. Р. Стивенс - «Алгоритмы. Теория и практическое применение»

4. Ф. Новиков - «Дискретная математика»

Приложение

Листинги программы

Файл MainWindow.py

import sys

from PyQt5. QtWidgets import *

import main

class Window(QMainWindow):

def __init__(self):

super().__init__()

self.initUI()

def initUI(self):

self.spin = QSpinBox(self)

self.spin.setMaximum(8)

self.spin.setMinimum(1)

self.spin.move (30, 440)

self.tx = QTextEdit(self)

self.tx.setFixedSize (330, 400)

self.tx.move (30,30)

self.setFixedSize (390, 550)

self.setWindowTitle ('Курсовой проект')

btn1 = QPushButton («Генерация», self)

btn1.move (30, 470)

btn1.clicked.connect (self.buttonClicked)

self.show()

def buttonClicked(self):

numb = 1

list = main.main (int(self.spin.value()))

if list == [1]:

self.tx.append (str(list))

else:

for i in list:

if i[0] == numb:

self.tx.append (' ')

numb += 1

self.tx.append (str(i))

if __name__ == '__main__':

app = QApplication (sys.argv)

ex = Window()

sys.exit (app.exec_())

Файл main.py

a = []

b = []

list_of_sets = []

def append_in_list():

global a, list_of_sets

list_of_sets.append (a.copy())

def Algorith (i, n):

global a, b

if i == n:

append_in_list()

else:

for j in range(n):

if b[j] == 0:

b[j] = 1

a[i] = j + 1

Algorith (i+1, n)

b[j] = 0

def main(arg):

if arg == 1:

return [1]

global a, b, list_of_sets

list_of_sets.clear()

a = [0] * arg

b = [0] * a

n = arg

Algorith (0, n)

return list_of_sets

Размещено на Allbest.ru