Глава 2 порождение комбинаторных объектов


Глава 2 порождение комбинаторных объектов

Прямое применение алгоритма поиска с возвращением к перестановкам порождает их в лексикографическом порядке, т.е. получаемая последовательность для имеет вид (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Их также можно порождать следующим алгоритмом.

Начинаем с перестановки , а переход от текущей перестановки к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляем последовательным выполнением следующих действий:

1) просмотр справа налево в поисках самой правой позиции , в которой (если такой позиции нет, то текущая перестановка является последней и следует закончить порождение);

2) просмотр от слева направо в поисках наименьшего из таких элементов , что и ;

3) транспозиция (взаимная замена) элементов и и обращение отрезка путем транспозиции симметрично расположенных элементов (заметим, что элементы обращаемого отрезка расположены в порядке убывания).

Например, для и после выполнения первых двух шагов имеем и , а результат транспозиции и и обращения отрезка переводит в (2,6,7,1,3,4,5,8).

Доказательство того факта, что описанный алгоритм осуществляет корректное порождение перестановок в лексикографическом порядке, довольно просто и здесь не приводится (заметим, однако, что использование этого или любого другого метода в решении задания обязательно предполагает знание студентом доказательства его корректности).

Важность лексикографического порядка определяется его простотой и естественностью. Существенным недостатком его следует признать сравнительно большой объем той работы, которую необходимо выполнить для преобразования текущего объекта в объект, являющийся следующим в смысле лексикографического упорядочения. Например, при соседними являются перестановки (2,3,1) и (3,1,2), различающиеся во всех позициях. При порождении комбинаторных объектов (в частности, перестановок) стремятся использовать такое их упорядочение, при котором следующий объект строится по предыдущему наиболее просто. Для многих классов комбинаторных объектов удается найти так называемый порядок минимального изменения, минимизирующий объемы работы по переходу от текущего элемента к соседнему и, таким образом, приводящий к наилучшим временным характеристикам алгоритма порождения комбинаторных объектов данного класса.

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

Можно дать простое рекурсивное описание для процесса построения перестановок в таком порядке. Для единственная перестановка (1) удовлетворяет нашим требованиям. Если 1$» BORDER=0 height=33 w >, то из последовательности перестановок для множества строится последовательность перестановок для элементов за счет расширения каждой из перестановок вставкой элемента на каждое из возможных мест («промежутков» между элементами ), справа налево при нечетном или слева направо при четном .

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

while # 1 do
Вывести текущее значение ; ;
while m$ m$» BORDER=0 height=33 w >do end;
Осуществить транспозицию элементов и в ;
Осуществить транспозицию элементов и в Q
end.

При этом -1 означает сдвиг влево, +1 — вправо и 0 — отсутствие сдвига. В этом алгоритме каждая следующая перестановка получается из предыдущей за счет перемещения одного единственного элемента . Этот элемент сдвигается до тех пор, пока не достигнет границы или элемента, большего, чем он сам. В этом случае его сдвиг прекращается, направление сдвига меняется на противоположное, в дальнейшем сдвигается следующий меньший его элемент, который можно сдвинуть.

Корректность алгоритма можно доказать индукцией по , используя следующее свойство вектора направлений.

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

Глава 2 порождение комбинаторных объектов

Выкладываю сюда «Теоремы и задачи» в CHM формате.

P.S.: Надеюсь буду в дальнейшем обновлять этот файлик.
P.P.S.: Выложил новый файл с исправленными русско-язычными путями.

Глава 1. Переменные, выражения, присваивания.
1.1. Задачи без массивов
1.2. Массивы.
1.3. Индуктивные функции (по А.Г.Кушниренко).

Глава 2. Порождение комбинаторных объектов.
2.1. Размещения с повторениями.
2.2. Перестановки.
2.3. Подмножества.
2.4. Разбиения.
2.5. Коды Грея и аналогичные задачи.
2.6. Несколько замечаний.
2.7. Подсчет количеств.

Глава 3. Обход дерева. Перебор с возвратами.
3.1. Ферзи, не бьющие друг друга: обход дерева позиций

Глава 4. Сортировка.
4.1. Квадратичные алгоритмы.
4.2. Алгоритмы порядка n log n.
4.3. Применения сортировки.
4.4. Нижние оценки для числа сравнений при сортировке.
4.5. Родственные сортировке задачи.

Глава 5. Конечные автоматы в задачах обработки текстов.
5.1. Составные символы, комментарии и т.п.
5.2. Ввод чисел

Глава 6. Типы данных.
6.1. Стеки.
6.2. Очереди.
6.3. Множества.
6.4. Разные задачи.

Глава 7. Рекурсия.
7.1. Примеры рекурсивных программ.
7.2. Рекурсивная обработка деревьев
7.3. Порождение комбинаторных объектов, перебор
7.4. Другие применения рекурсии


Глава 8. Как обойтись без рекурсии.
8.1. Таблица значений (динамическое программирование)
8.2. Стек отложенных заданий.
8.3. Более сложные случаи рекурсии.

Глава 9. Разные алгоритмы на графах.
9.1. Кратчайшие пути
9.2. Связные компоненты, поиск в глубину и ширину

Глава 10. Сопоставление с образцом.
10.1. Простейший пример.
10.2. Повторения в образце — источник проблем.
10.3. Вспомогательные утверждения
10.4. Алгоритм Кнута — Морриса — Пратта
10.5. Алгоритм Бойера — Мура
10.6. Алгоритм Рабина
10.7. Более сложные образцы и автоматы

Глава 11. Представление множеств. Хеширование.
11.1. Хеширование с открытой адресацией
11.2. Хеширование со списками

Глава 12. Множества и деревья.
12.1. Представление множеств с помощью деревьев.
12.2. Сбалансированные деревья.

Глава 13. Контекстно-свободные грамматики.
13.1. Контекстно-свободные грамматики. Общий алгоритм разбора.
13.2. Метод рекурсивного спуска.
13.3. Алгоритм разбора для LL(1)-грамматик.

Глава 14. Синтаксический разбор слева направо (LR)
14.1. LR-процессы
14.2. LR(0)-грамматики.
14.3. SLR(1)-грамматики
14.4. LR(1)-грамматики, LALR(1)-грамматики

Study & Dev О программировании и не только

Структуры данных и алгоритмы. Теория. Порождение и перебор комбинаторных объектов

January 10, 2007

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

  • последовательности;
  • перестановки;
  • множество подмножеств заданного множества и т.д.

Схема перебора всегда будет одинакова:

  • во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);
  • во-вторых, научиться переходить от произвольного элемента к непосредственно следующему за ним, данное требование очень важно, т.к. возвращаться к пропущенным в процессе перебора элементам будет сложнее, чем задать алгоритм сплошного перебора.

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

  1. X = First
  2. Пока X != Last
  3. X = Next (X)
  4. Конец

А теперь мы рассмотрим конкретные алгоритмы генерации последовательностей.

Перестановки

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. Необходимо отметить, что в перестановках порядок следования элементов важен и в перестановке должны быть задействованы все N элементов.
Количество перестановок для N элементов порядка N!. Действительно: на первое место может быть помещен любой из N элементов (всего вариантов N), на вторую позицию (N-1) элементов, итого вариантов N*(N-1), и если продолжить данную последовательность для всех мест, то получим: N*(N-1)*(N-2)* . *1;

Рассмотрим задачу получения всех перестановок чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу). Существует много алгоритмов генерации перестановок, которые отличаются порядком получаемых перестановок. Наиболее известна лексикографическая перестановка.

Это значит, что перестановки сравниваются слева направо, поэлементно и большей из них является та, в которой встретился элемент, который больше за соответствующий ему элемент в другой перестановке.
Рассмотрим пример генерации перестановок: предположим, что необходимо получить все перестановки чисел 1,2,3,4,5. первой перестановкой будет (1,2,3,4,5), а последней (5,4,3,2,1). Предположим, что на некотором шаге работы была получена перестановка P = (3,4,5,2,1) = (p1, p2, p3,p4, p5).

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

  • Необходимо просмотреть перестановку S справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент массива с большим номером) был не более чем предыдущий (элемент массива с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться. В нашем примере это элемент p2 .
  • Снова просмотрим пройденный путь (справа налево) пока не дойдем до первого числа, которое больше чем отмеченное нами p2, это p3.
  • Необходимо поменять местами элементы p2 и p3.
  • Теперь в части массива, которая размещена справа от позиции p3 (после перемещения) надо отсортировать все числа в порядке возрастания. Благодаря тому, что до этого они все были уже записаны в порядке убывания необходимо данную подпоследовательность просто перевернуть. Таким образом мы получим новую последовательность S=(3,5,1,2,4). Которая будет рассматриваться при генерации следующей перестановки.


Замечание: на практике при генерации перестановок никогда не выполняют обмены непосредственно информационных элементов. Например, если у нас есть класс, описывающий студента — “Student” и нам необходимо получить перестановки студентов группы, то принято создать массив с порядковыми номерами студентов и выполнять перестановки именно на этом массиве, а по порядковому номеру обращаться к соответствующему объекту студента.

Илон Маск рекомендует:  Что такое код swfmovie >streammp3

Задание: получить перестановку лексикографически следующую за (5,4,6,2,1,3).

Пример исходного кода алгоритма генерации всех перестановок в лексикографическом порядке.

Сочетания

Сочетания представляют собой наборы элементов, которые отличаются хотя бы одним элементом, и каждый из которых (каждый набор) содержит всегда M элементов, взятых из разных N элементов. Важно, что в сочетаниях порядок следования элементов не учитывается.

Пример : из элементов S=(a,b,c), можно получить следующие сочетания по два: C1 = a,b; C2=b,c; C3=a,c;

Количество сочетаний из N элементов по M обозначают С(N,M)=N!/(M!*(N-M)!) = C(N, N-M).

Упражнение: докажите правильность последнего равенства.

Рассмотрим алгоритм генерации сочетаний.

Раз порядок элементов в соединении не существенен, то получаемые выборки элементов будем упорядочивать в порядке возрастания. В качестве начальной конфигурации возьмем S=(1,2, . M), т.е. B[j] = j, для j [1..M]. Сочетания будем получать в возрастающем лексикографическом порядке, т.е. последним сочетанием будет S=(N-M+1, N-M+2, . N). Для каждого элемента последнего сочетания будет выполняться условие: B[i] = N-M+i. Для генерации очередного сочетания необходимо найти элемент B[i] с максимальным индексом j, таким чтобы выполнялось условие: B[i] j, положим значение B[K] = B [K-1] + 1. Если же такого B [i] не существует, то генерация сочетаний длины M завершена.

Задание: Какое сочетание будет сгенерировано вышеописанным алгоритмом следом за сочетанием (3,5,8), когда N =8, M=3.

Размещения

Сочетания, которые отличаются друг от друга составом элементов или их порядком, каждое из которых состоит из M (M N .

Упражнение: докажите истинность данной формулы.

Для генерации всех подмножеств используется массив B [0..N], отметьте, что количество элементов массива на 1 больше чем необходимое, 0-ой элемент – фиктивный и используется для оптимизации алгоритма, и признака его завершения. Элементы массива будут принимать только два значения 1, 0 или TRUE, FALSE – соответственно, если элемент включается в выборку или не включается. Т.е. пустому множеству будет соответствовать массив со всеми нулями, а подмножеству, содержащему все элементы оригинального множества – массив в котором все элементы будут 1, или TRUE.

Если генерировать числа в диапазоне от 0 до 2N-1, и каждое из них переводить в двоичную систему счисления, то это представление совпадет с распределением нулей и единиц в массиве B. Будем считать это схемой 1.

Разумеется что задача перевода числа в двоичную систему требует затрат ресурсов, которых можно было бы избежать, поэтому мы будем моделировать операции сложения над числом в виде массива. Это схема # 2. При сложении массива с 1-ей мы будем просматривать массив B справа налево, заменяя единицы нулями до тех пор, пока не нейдем нуль, в который занесем единицу. Генерация подмножеств будет завершена, как только B [N] станет равным 1.

Далее приводится пример рекурсивного решения данной задачи. Разберитесь в нем.

Задание: Создайте согласно описанной схеме 2 версию не рекурсивного алгоритма генерации множества всех подмножеств заданного множества.

Сочетания с повторениями

Размещения с повторениями

Размещения, которые мы рассматривали ранее, предполагали, что из N разных элементов в очередное соединение входил только один раз. Также выделяют размещения с повторениями, в таком виде размещений каждый из N элементов в очередное размещение по M элементов может входить несколько раз. Итак, размещением с повторениями называют такие размещения из N элементов по M, в которых один и тот же элемент может повторяться в каждом из размещений любое количество раз, но не более чем M раз.

Пример: для элементов a,b размещения с повторениями из 2 по 3 будут следующими:
Всего количество подобных размещений обозначается и будет составлять величину порядка:

Пример: Вася Тапкин положил в камеру хранения на вокзале свой багаж, и забыл код доступа, правда при этом он помнит, что в коде не было цифр 0,1,5. требуется найти сколько вариантов ему потребуется перебрать пока он не откроет свою ячейку? Здесь необходимо вычислить число размещений из (10-3) цифр на место 5-ти ключей, причем именно с повторениями. Следовательно, суммарное количество всех вариантов будет A = 7^5 = 16 807.

Для того чтобы создать алгоритм генерации списка всех размещений, вам сначала надо будет разобраться в том, почему именно такая формула (***) задает количество размещений. Если вы все еще помните начало учебного курса, когда вас знакомили с различными системами исчисления, то заметите, что если мы пронумеруем все элементы, участвующие в размещение номерами от 0 до N-1, по-порядку, то каждому из размещений можно поставить в соответствие некоторое число в N-ичной системе счисления, которое состоит из M цифр. Данное множество чисел будет принимать все значения от 00000 (итак все M нулей), до ((N-1)(N-1)…). Например, если вы посмотрите на первый пример с размещениями букв a, b, то, заменив букву “a” на ноль, а букву “b” на единицу, мы получим:
Пример кода алгоритма, который генерирует все размещения с повторениями, приводится далее:


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

Перестановки из N элементов, в каждую из которых входят N1 одинаковых предметов одного типа, N2 одинаковых предметов другого типа и так далее, это требование выполняется для K различных групп предметов (очевидно, что N1+N2+ … + NK = N) называются перестановками из N элементов с повторениями:

Пример: перестановки из двух элементов a, b каждый из которых будет взят по два раза:
Количество перестановок с повторениями может быть вычислено по следующей формуле:

Пример: в кондитерском магазине продаются четыре вида пирожных. Необходимо ответить на вопрос: сколькими способами можно купить 7 пирожных.

Это задача на подсчет количества сочетаний из N = 4 по M = 7. Согласно приведенной выше формуле: C = 10!/(7!3!) = 120.

Для того чтобы разобраться в непосредственно алгоритме генерации сочетаний следует внимательно прочитать доказательство корректности формулы (***).

Каждое сочетание с повторениями кодируют с помощью нулей и единиц: сначала записывается столько единичек сколько было взято элементов первого типа. Затем чтобы отделить элементы первого типа от элементов второго типа мы записываем один нолик. А затем – снова единицы – столько раз сколько у нас элементов второго типа. Потом снова ноль и так далее. Так для ранее приведенных сочетаний (**) мы получим следующие двоичные последовательности:
Таким образом количество сочетаний с повторениями из N элементов по M будет равно количеству перестановок с повторениями, которые можно получить из M единиц и (N-1) нулей. Для того чтобы подсчитать эту величину применяется формула из предыдущей темы.

Оптимизация переборных задач

Часто встречаются задачи, в которых трудно найти решение отличное от полного перебора. Мы уже умеем выполнять типовые задачи перебора, однако следует помнить, что часто количество перебираемых вариантов слишком велико и подлежит оптимизации. В качестве примеров переборных задач можно привести: получить все четырехзначные числа, у которых все цифры нечетные. Так для решения данной задачи применяются алгоритм генерации всех размещений из пяти элементов (1,3,5,9) по 4.

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

Пример: двум медвежатам очень повезло: они в лесу нашли несколько кусков сыра и теперь хотят поделить их поровну. Т.е. каждому из них должен достаться одинаковый вес, может быть разным количеством кусков сыра. Например, если даны следующие куски сыра: 3, 7, 2, 5, 1 то их можно разделить, например, так: 7,2 и 3, 5, 1. Если же нам даны такие куски сыра: 1, 3, 7, 2 то их разделить не возможно. Предполагается, что вес каждого куска сыра является целым.

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

Первым шагом, разумеется, будет определение суммарного веса сыра “S” подлежащего разделу. В случае если это число будет нечетным, то раздел не возможен. Первое решение, которое приходит в голову всем начинающим программистам – это воспользоваться алгоритмом генерации всех подмножеств заданного множества, очевидно, что таким образом можно будет перебрать все возможные варианты раздела, каждый из которых необходимо оценить – равна ли сумма получившегося подмножества половине S. Однако данный алгоритм определяется O(2^N) – что является быстро растущей функцией и, следовательно, неприменим в ситуациях, когда количество кусков сыра велико. Для оптимизации количества переборов можно использовать следующие положения:

  • очевидно, что нас не должны интересовать такие подмножества, в которых сумма элементов превосходит S/2. Таким образом, когда мы сгенерировали подмножество с весом S/2 все остальные множества, получающиеся из данного путем добавления к нему некоторых других элементов, нас не будут интересовать.
  • Имеет смысл отдать самую большой кусок сыра одному из медвежат (в любом случае кто-то его должен получить), но благодаря этому мы уменьшим сумму, которую нам необходимо набрать из оставшихся элементов – следовательно, благодаря п.1 уменьшится также и количество перебираемых элементов. Следовательно, имеет смысл куски сыра отсортировать по величине.
  • Если один из кусков сыра имеет вес равный половине искомой суммы S, то разбиение найдено.
  • Если хотя бы один из кусков сыра имеет вес более чем S/2 то разбиение не возможно.

Глава 10. Комбинаторика. Комбинаторные конфигурации

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

Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить П Предметов по Т Ящикам называется, Числом размещений И обозначается U(M,N).

Каждый из N предметов можно разместить M способами.

При игре в кости бросаются две кости и выпавшие на верхних гранях очки скла­дываются. Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции F: <1,2>® <1,2,3,4,5,6>(аргумент — номер кости, ре­зультат — очки на верхней грани). Таким образом, всего возможно U(6,2) = 62 = 36 различных исходов. Из них только один (6 + 6) дает двенадцать очков. Вероятность 1/36.

Размещения без повторений

Число инъективных функций, или число всех возможных способов разместить П Предметов по M ящикам, не более чем по одному в ящик, называется Числом размещений без повторений И обозначается А(M, п) или [M]n, или (M)n.

Ящик для первого предмета можно выбрать M способами, для второго — M — 1 способами, и т. д. Таким образом,

По определению считают, что А(Т, N) = 0 при П > Т И А(Т, 0) = 1.

В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. Сколько возможно раз­личных исходов, если в соревновании участвуют П Участников? Каждый воз­можный исход соответствует функции F: <1,2,3>® <1..N> (аргумент — номер призового места, результат — номер участника). Таким образом, всего возможно А(П,3) = П(П — 1)(N — 2) различных исходов.

Илон Маск рекомендует:  Виде о сайте, создании сайтов


Число взаимнооднозначных функций, или Число перестановок п Предметов, обо­значается Р(П).

Последовательность E = (E1. Em) непустых подмножеств множества Е (E Ì 2E, Ei Ì Е, Ei ¹ Æ) называется Цепочкой В Е, Если

Цепочка E называется Полной Цепочкой в Е, Если |E| = |Е|. Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмноже­ство Ei+1 получено из предыдущего подмножества Ei Добавлением ровно одного элемента из Е И, таким образом, |E1| = 1, |E2| = 2, . |Ет| = |Е| = т. Следова­тельно, полная цепочка определяется порядком, в котором элементы Е Добавля­ются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек — это количество перестановок элементов множества Е, Рав­ное M!.

Число строго монотонных функций, или число размещений П Неразличимых предметов по Т Ящикам, не более чем по одному в ящик, то есть число способов выбрать из m ящиков N ящиков с предметами, называется Числом сочетаний И обозначается С(Т, п) или или .

1. Число размещений без повторений нужно разделить на число перестановок, поскольку предметы неразличимы.

2. Число сочетаний является числом строго монотонных функций, потому что строго монотонная функция F: 1..п ® L..M определяется набором своих значений, причем 1£ F(1) M.

В начале игры в домино каждому играющему выдается 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементного множества. Имеем:

Сочетания с повторениями

Число монотонных функций, или число размещений N неразличимых предме­тов по M ящикам, называется Числом сочетаний с повторениями И обозначается V(M, N).

Сколькими способами можно рассадить N Вновь прибывших гостей среди M Го­стей, уже сидящих за круглым столом? Очевидно, что между то сидящими за круглым столом гостями имеется M Промежутков, в которые можно рассаживать вновь прибывших. Таким образом, это можно сделать

Школа179

Порождение комбинаторных объектов

Решения задач на порождение комбинаторных объектов в своей основе имеют одну и ту же схему, которая предполагает ответ на следующие вопросы:

  1. Каков порядок порождения комбинаций? (иногда это оговорено в условии)
  2. Как получить первую комбинацию?
  3. Как, имея заданную комбинацию, получить следующую?
  4. Как проверить, является ли текущая комбинация последней?

Примечание: вопросы 2 и 4, как правило, решаются крайне легко

Сама же процедура порождения всех комбинаций обычно имеет следующий вид:

процедура получитьВсеКомбинации
| получитьПервуюКомбинацию
| вывести Комбинацию
| пока не текущаяКомбинацияПоследняя выполнять
| | получитьСледующуюКомбинацию
| | вывести Комбинацию
| конецЦикла
|конецПроцедуры

В задачах этого листка:

  • Использование вышеописанной процедуры и, таким образом, всех ее подпрограмм обязательно .
  • Рекурсия запрещена .
  • Для хранения комбинаций используется глобальный массив и соответствующие константы; данные с клавиатуры не вводятся .
  • Время выполнения процедурыполучитьСледующуюКомбинацию , по умолчанию не более C n.

Задачи

07_01a (0)
Напечатать все последовательности длины n из чисел 0.. k-1 в лексикографическом порядке

07_01b (1)
Напечатать все последовательности длины n из чисел 0.. k-1 в обратном лексикографическом порядке

07_01c (2)
Напечатать все последовательности длины n у которых i-ый член не превосходит i.

07_01d (4)
Напечатать все последовательности длины n из чисел 0.. k-1 так, чтобы соседние последовательности отличались бы только в одной позиции и только на единицу.


07_02 (3)
Напечатать все подмножества множества 1 .. k.

07_03a (4)
Напечатать все перестановки чисел 1 .. n, то есть последовательности длины n, в которые каждое из этих чисел входит по одному разу.

07_03x (3)
Написать функцию int nPermut(int *perm, int n) , которая по заданному n и перестановке первых n чисел perm возвращает ее номер при лексикографическом перечислении.
пример 1: при n=5 и perm[] = <1, 2, 3, 4, 5>возвращается 1.
пример 2: при n=4 и perm[] = <1, 2, 4, 3>возвращается 2.
пример 3: при n=3 и perm[] = <3, 2, 1>возвращается 6.

07_03y (3)
Написать функцию int *permutByNum(int k, int n) , обратную к функции из предыдущей задачи по заданному n и
номеру k перестановки первых n чисел при лексикографическом перечислении возвращает указатель на массив с этой перестановкой.
пример 1: при n=5 и k= 1 permutByNum возвращается указатель на <1, 2, 3, 4, 5>.
пример 2: при n=4 и k= 2 permutByNum возвращается указатель на <1, 2, 4, 3>.
пример 3: при n=3 и k= 6 permutByNum возвращается указатель на <3, 2, 1>.

07_03b (5)
То же, что и в 07_03a но еще так, чтобы соседние последовательности получались бы друг из друга обменом лишь двух элементов.

07_04 (2)
Перечислить все возрастающие последовательности длины k из чисел 1 .. n в лексикографическом порядке.
пример: при n=5, k=2 получаем 12 13 14 15 23 24 25 34 35 45)

07_05a (4)
Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). разбиения представляются как невозрастающие последовательности, порядок перечисления – лексикографический.
пример: для n = 4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

07_05b (4)
Представляя по-прежнему разбиения как невозрастающие последовательности, переписать их в порядке, обратном лексикографическому.
пример: для n = 4, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).

07_05c (4)
Представляя разбиения как неубывающие последовательности, перечислить их в лексикографическом порядке.
пример: для n = 4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4;

07_06 (3)
Перечислить все вложения (т. е. функции, переводящие разные элементы в разные) множества <1..k> в <1..n>, где k не превышает n.

07_07 (4)
Перечислить все последовательности нулей и единиц длины 2n, содержащие n нулей и n единиц, такие, что в любом их начальном отрезке число единиц не превосходит числа нулей.

07_08 (4)
На окружности задано 2n пронумерованных точек Перечислить все способы провести nнепересекающихся хорд, с вершинами в этих точках.

07_09 (4)
Перечислить все способы разрезать выпуклый n–угольник на треугольники, проведя n–3 его диагонали.

07_10 (5)
Перечислить все способы расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий.
пример: для n = 4 существует 5 расстановок:

  1. ((a. b)..c)..d
  2. .(a..(b. c)).d
  3. .(a. b).(c. d)
  4. ..a.((b. c)..d)
  5. ..a..(b..(c. d))

Порождение комбинаторных объектов

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

2.1. Размещения с повторениями

2.1.1. Напечатать все последовательности длины k из чисел 1..n .

Решение. Будем печатать их в лексикографическом порядке (последовательность a предшествует последовательности b , если для некоторого s их начальные отрезки длины s равны, а (s+1) -ый член последовательности a меньше). Первой будет последовательность , последней — последовательность . Будем хранить последнюю напечатанную последовательность в массиве x[1]..x[k] .

Опишем, как можно перейти от x к следующей последовательности. Согласно определению, у следующей последовательности первые s членов должны быть такими же, а (s+1) -ый — больше. Это возможно, если x[s+1] меньше n . Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непосредственно следующей). Соответствующее x[s+1] нужно увеличить на 1 . Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший n (он найдется, т.к по предположению x<>last ), увеличить его на 1 , а идущие за ним члены положить равными 1 .

Замечание. Если членами последовательности считать числа не от 1 до n , а от 0 до n-1 , то переход к следующему соответствует прибавлению единицы в n -ичной системе счисления .

2.1.2. В предложенном алгоритме используется сравнение двух массивов ( x <> last ). Устранить его, добавив булевскую переменную l и включив в инвариант соотношение

2.1.3. Напечатать все подмножества множества <1. k>.


Решение. Подмножества находятся во взаимно однозначном соответствии с последовательностями нулей и единиц длины k .

2.1.4. Напечатать все последовательности положительных целых чисел длины k , у которых i -ый член не превосходит i .

2.2. Перестановки

2.2.1. Напечатать все перестановки чисел 1..n (то есть последовательности длины n , в которые каждое из этих чисел входит по одному разу).

Решение. Перестановки будем хранить в массиве x[1]..x[n] и печатать в лексикографическом порядке. (Первой при этом будет перестановка , последней — . Для составления алгоритма перехода к следующей перестановке зададимся вопросом: в каком случае k -ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (т.е. членов с номерами больше k ). Мы должны найти наибольшее k , при котором это так, т.е. такое k , что

Алгоритм перехода к следующей перестановке :

Замечание. Программа имеет знакомый дефект: если t=n , то x[t+1] не определено.

Комбинаторика: основные правила и формулы.

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены:

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?


Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m ( ) из этих (n*r) предметов?

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Илон Маск рекомендует:  Таблицы стилей

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

Размещения без повторений. Размещения с повторениями

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

Перестановки без повторений. Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Глава 2 порождение комбинаторных объектов


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

7.3.1. Написать программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1..k (их количество равно k в степени n).

Решение. Программа будет оперировать с массивом a[1]..a[n] и числом t. Рекурсивная процедура generate печатает все последовательности, начинающиеся на a[1]..a[t]; после ее окончания t и a[1]..a[t] имеют то же значение, что и в начале:

Типы комбинаторных задач

Читайте также:

  1. Cущность менеджмента, цели и задачи
  2. I. Основные задачи обеспечения безопасности и информации в информационных системах
  3. II Каково место задач в учебном процессе.
  4. Автоматизация комплекса задач по учету основных средств
  5. Алгоритм решения задачи
  6. Анализ задачи формирования модели измерения
  7. Аналитический способ представления задачи 1
  8. Арбитражные суды, их роль и основные задачи
  9. Базы данных, используемые при решении задач маркетинга
  10. БД (Б2), включающая информацию для решения задач планирования и учёта
  11. Будьте реалистами и не ставьте перед собой задачи, которые не сможете решить.
  12. Важнейшие международные статистические стандарты, цели и задачи их использования

Типы комбинаторных проблем

Проблемы и задачи комбинаторики

Лекция 1.

Комбинаторика изучает приёмы нахождения числа различных комбинаций, составленных из данных предметов (элементов дискретного множества предметов) при определённых условиях.

Комбинация – некоторое сочетание предметов.

1. Проблемы существования. Доказывается теоретически, что есть решение или нет.

2. Если решения задачи есть, то сколько их.

3. Выбрать наиболее экономичный способ решения.

1. Задача о маршрутах.

2. Задача о размещении.

3. Задача о покрытии.

4. Задача об укладке.

5. Задача о разбиении.

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

Пусть S – множество из n элементов (|S|=n). Говорят, что S – n-множество.

T1 T2 Tn

Задача о покрытии

Найти такие множества Ti, i = 1, 2, …, r, чтобы (чтобы объединение этих множеств «покрыло» S). Например, застелить весь пол в комнате несколькими коврами. Ковры могут накладываться друг на друга (множества могут пересекаться), но незакрытых участков пола быть не должно.

Во многих задачах покрытие должно быть наиболее экономичным (так называемое минимальное покрытие), когда число множеств Ti должно быть минимальным, сами они должны содержать минимально возможное число элементов.

Задача о укладке


Найти такие попарно непересекающиеся множества Ti, i = 1, 2, …, r, (Ti ÇTj = Æ при i¹j) чтобы (чтобы объединение этих множеств вошло в S). (нарисовать)

Например, уложить несколько предметов в одну коробку. Между предметами могут быть пустые промежутки, но сами предметы друг с другом не пересекаются и укладываются в коробку.

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

Задача о разбиении

Найти такие попарно непересекающиеся множества Ti, i = 1, 2, …, r, (Ti ÇTj = Æ при i¹j) чтобы (чтобы объединение этих непересекающихся множеств дало S). (нарисовать)

Например, группы в институте – это разбиение множества студентов института. Группы не пересекаются, а их объединение дает множество всех студентов института.

Дата добавления: 2014-01-05 ; Просмотров: 1799 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Дискретка_Экзамен_Ответы / комб / 2 Теоремы о количестве комбинаторных объектов

Теорема 2.1. Количество всех различных подмножеств n-элементно-го множества равно 2 n .

Доказательство. Поставим в соответствие каждому подмножеству А множества В n-разрядный двоичный вектор, i-ый разряд которого равен единице только тогда, когда i-ый элемент множества В принадлежит подмножеству А. Для того, чтобы сформировать n-разрядный двоичный вектор, нужно выполнить одно за другим n действий: заполнить 1-ый разряд вектора, 2-ой разряд и так до n-го разряда. Каждое действие можно выполнить двумя способами (разряд двоичного вектора можно заполнить только нулём или единицей). По правилу произведения все n действий могут быть выполнены 222=2 n способами, т.е. может быть получено 2 n различных n-разрядных двоичных векторов, следовательно, количество всех различных подмножеств n-элементного множества равно 2 n .

Теорема 2.2. Количество всех различных перестановок n-элемент-ного множества М (количество способов упорядочивания множества) определяется формулой Рn=n!.

Доказательство. Перестановку можно представить последовательностью из n мест. Для того чтобы получить одну перестановку, нужно выполнить одно за другим n действий: заполнить 1-ое место в последовательности, 2-ое место и так до n-го места. Для выполнения 1-го действия (заполнения 1-го места) можно взять любой элемент из множества М и поставить его на 1-ое место, т.е. его можно выполнить n-способами, и после этого в множестве М останется n-1 элемент. Для выполнения 2-го действия (заполнения 2-го места) можно взять любой элемент из оставшихся в множестве М и поставить его на 2-ое место, т.е. его можно выполнить n-1-способами, и после этого в множестве М останется n-2 элемента и т.д. По правилу произведения все n действий могут быть выполнены n(n-1)(n-2). 21=n! способами, следовательно, количество всех различных перестановок n-элементного множества равно n!.

Теорема 2.3. Количество всех различных размещений n-элементного множества М по k местам определяется формулой

Доказательство. Размещение можно представить последовательностью из k мест. Для того чтобы получить одно размещение, нужно выполнить одно за другим k действий: заполнить 1-ое место в последовательности, 2-ое место и так до k-го места. Для выполнения 1-го действия (заполнения 1-го места) можно взять любой элемент из множества М и поставить его на 1-ое место, т.е. его можно выполнить n-способами, и после этого в множестве М останется n-1 элемент. Для выполнения 2-го действия (заполнения 2-го места) можно взять любой элемент из оставшихся в множестве М и поставить его на 2-ое место, т.е. его можно выполнить n-1-способами, и после этого в множестве М останется n-2 элемента и т.д. до k-го места. По правилу произведения все k действий могут быть выполнены

способами, следовательно, количество всех различных размещений n-элементного множества М по k местам равно .

Теорема 2.4. Количество всех различных размещений с повторениями n-элементного множества М по k местам равно n k .

Доказательство. Для того чтобы получить одно размещение с повторениями, нужно выполнить одно за другим k действий: заполнить 1-ое место в последовательности, 2-ое место и так до k-го места. Для выполнения каждого действия можно взять любой элемент из множества М и поставить его на соответствующее место, т.е. каждое из k действий можно выполнить n способами. По правилу произведения все k действий могут быть выполнены nnn=n k способами, следовательно, количество всех различных размещений с повторениями n-элементного множества по k местам равно n k .

Теорема 2.5. Количество всех различных сочетаний из n элементов по k определяется формулой .

Доказательство. Можно получить все размещений, упорядочив всеми возможными способами каждое из сочетаний. Количество способов упорядочивания одного сочетания равно k!, следовательно = k! . Отсюда .

Теорема 2.6. Число перестановок с повторениями для мультимножества S=1*s1,n2*s2. nk*sk> выражается формулой , где .

Доказательство. Рассмотрим одну перестановку мультимножества и заменим в ней все одинаковые элементы разными. Тогда, число различных перестановок, которые можно составить из рассматриваемой, равно n1!n2!…nk!. Проделав это для каждой перестановки, получим n! перестановок. Следовательно, Pn(n1,n2,…,nk)n1!n2!…nk!=n!. Отсюда

Теорема 2.7. Количество различных сочетаний из n элементов по k с повторениями равно .

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

1100, 1010, 1001, 0110, 0101, 0011.

Таким образом, каждому сочетанию с повторениями из n по k соответствует последовательность из k единиц и n-1 нулей. Количество таких последовательностей равно числу способов, которыми можно выбрать n-1 мест для нулей из n+k-1 общего числа мест ( ), или, то же самое, — числу способов выбора k мест для единиц из n+k-1 мест ( ).

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL