Комбинаторика.

Вычисление факториала.

Этот алгоритм я сделал одним из первых когда пробовал "Редактор блок-схем" поэтому и сюда его добавил. Хотя особой необходимости в нем нет. Наверх

Нахождение числа сочетаний .

Функция находит число сочетаний из n элементов по m:

Вычисления проводятся по рекурентной формуле:

Наверх

Процедура находит перестановку следующую за данной в лексикографическом порядке. Начальная перестановка задается в массиве X туда же после работы процедуры помещается найденная перестановка. Переменная END равна истине, если на вход подана перестановка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все перестановки n - чисел надо инициализировать массив X значениями 1,2,. . ., n и последовательно вызывать процедуру до тех пор пока значение переменной END не окажется равным истине.

Заметим, что количество перестановок из n чисел будет равно факториалу числа n. Наверх

Задача о коммивояжере (методом комбинаторики).

Процедура находит решение задачи о коммивояжере, используя предыдущий алгоритм для получения всех возможных путей. На вход процедуры подается матрица цен на билеты W при этом, если нет пути из одного города в другой, то соответствующий элемент матрицы равен 10Е6. Матрица не обязательно симметричная. В переменной f находится номер города из которого коммивояжер начинает путешествие. Затем используя алгоритм получения перестановок перебираются все возможные пути (с началом в городе f) и вычисляется их цена и таким образом находится путь минимальный по затратам, который помещается в массив x.

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

Выборки из n элементов по m.

Процедура находит выборку следующую за данной в лексикографическом порядке. Начальная выборка задается в массиве X туда же после работы процедуры помещается найденная выборка. Переменная END равна истине, если на вход подана выборка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все выборки - надо инициализировать массив X значениями 1,2,. . ., m и последовательно вызывать процедуру до тех пор пока значение переменной END не окажется равным истине. Числа внутри выборки, поданной на вход процедуры, должны быть упорядочены по возрастанию.

Заметим, что количество выборок m из n равно числу сочетаний m из n и вычисляется с помощью этого алгоритма. Наверх

Выборки из n элементов по m (2-й способ).

Процедура находит все выборки из n элементов по m. Этот алгоритм мне прислал Александр, и он основан на подходе отличном от того что применялся в предыдущем алгоритме.

Все полученные выборки будут помещаться в массив X: array [1..m,1..CMN] of integer. Размер СMN соответствует количеству выборок m из n и равно числу сочетаний m из n, которое вычисляется с помощью этого алгоритма.

Суть алгоритма в следующем. Выборку можно представить в виде набора длины n 0 и 1, при этом если элемент с номером k участвует в выборке, то в наборе ему соответствует 1, если не участвует, то 0. Такой набор представляет некоторое целое число a ≤ 2n-1в двоичной системе. Мы будем перебирать целые числа в возрастающем порядке и если у них в двоичном представлении ровно m единиц помещать соответствующую выборку в массив X. Осталось определиться с пределами внутри которых надо перебирать целые числа, но это достаточно очевидно. Начать надо с числа в двоичном представлении которого первые m мест занимают единицы 1...10...02=2m-1, а закончить числом 0...01...12=2n-2n-m.

В блок-схеме используется оператор a shr b для обозначения сдвига вправо битового представления числа a на b бит. И соответственно оператор a shl b для сдвига в влево.

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

Решение задачи о рюкзаке.

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

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