Решение задач по комбинаторике. Алгоритмы по комбинаторике.

Всего таких перестановок будет N!=N*(N-1)*...*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров.

Эта задача реализуется следующим рекурсивным алгоритмом поиска с возвращением (все слова набора A упорядочены по номерам):

Предложим простой способ построения всех разбиений числа.

Эту задачу решил больше 200 лет тому назад великий математик Леонард Эйлер.

Элементы исходной последовательности-алфавита различны, слово зависит от порядка букв. Если в исходной последовательности есть одинаковые буквы, то надо будет кое-что подкорректировать (их-то порядок не важен будет в слове, если стоят рядом).

Алгоритм: будем генерировать числа от 0 до 2ⁿ-1, находить их двоичное представление, и формировать подмножество из элементов с индексами единичных битов в этом представлении.

Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.