4.6. Порождение сочетаний

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

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

Алгоритм 4.11. Порождение сочетаний

(см. скан)

Задача. Выпуклый многоугольник. Дано множество пар целых чисел координаты точек на плоскости. Написать программу выделения тех точек из заданного множества, которые являются вершинами выпуклого многоугольника, содержащего все остальные точки. Исходные данные представлены в текстовом файле, имеющем следующую структуру. Первым числом в файле является целое количество точек. Последующие числа определяют пар целых координаты точек. Результаты расчетов, признаки принадлежности исходных точек выпуклому многоугольнику: точка не принадлежит, 1 — точка принадлежит, сохранить в текстовом файле.

Пример файла исходных данных:

Выходной файл для данного примера:

Решение. Если не применять специальных методов, то в качестве решения можно использовать следующий алгоритм. Ясно, что точка является вершиной выпуклого многоугольника, если она не лежит ни в одном треугольнике, вершинами которых являются исходные точки без рассматриваемой точки Всего треугольников из точек можно составить Тогда сложность задачи полного перебора треугольников для каждой точки (х, у,) составит Реализация данного подхода представлена программой на языке Pascal в алгоритме 4.12.

Алгоритм 4.12. Программа поиска точек выпуклой оболочки

(см. скан)

(см. скан)