Как перебрать все перестановки и о факториальном разложении натуральных чисел / Хабр
Задачи о переборе всех возможных перестановок заданного множества сущностей возникают в программировании достаточно часто. Как известно из комбинаторики, число возможных перестановок n предметов равно попросту факториалу числа n
n! = n * (n — 1) * (n – 2) * … * 3 * 2 * 1
Факториал – достаточно быстро растущая функция, об этом говорит ее асимптотика (формула Стирлинга), хотя достаточно посмотреть на факториалы нескольких первых членов натурального ряда:
1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000
Как видно, факториал 13-ти уже не умещается в тип данных long.
Если задаться целью найти однозначное соответствие между номером перестановки — числом в диапазоне от 1 до n! – и ее реализацией, можно натолкнуться на один очень интересный математический факт.
Для начала вспомним понятие позиционной системы счисления. Вклад каждого разряда числа в его значение в позиционной системе по основанию K есть разряд, умноженный на основание K в степени, равной позиции разряда в записи числа. Основание системы счисления обычно пишут как подстрочный индекс, таким образом
196610 = 1*103 + 9 * 102 + 6 * 101 + 6 (*100)101100012 = 1 * 27 + 0 * 26 + 1 * 25 + 1 * 24 + 0 * 23 + 0 * 22 + 0 * 21 + 1 * 20 (=17710)
Позиционная запись, помимо компактности, обладает тем бесценным свойством, что алгоритм выполнения арифметических операций оказывается чрезвычайно простым (есть историческая байка, что в школах средневековья изучение арифметики занимало несколько лет, поскольку вычисления над числами в НЕпозиционной римской записи имели множество правил для того, чтобы провести простое сложение!)
Оказывается, существует, и является однозначным разложение и способ записи числа, в котором каждый разряд в таком его представлении умножается на ФАКТОРИАЛ номера позиции.
Покажем это на примерах:
1985 = 2 * 6! + 4 * 5! + 2 * 4! + 2 * 3! + 2 * 2! + 1 * 1!2 940 861 129 405 = 2*15! + 3*14! + 10*13! + 3*12! + 6*11! + 8*10! + 4*9! + 8*8! + 0*7! + 2*6! + 2*5! + 1*4! + 3*3! + 1*2! + 1*1!
В обычной позиционной системе значение каждого разряда должно быть строго меньше основания. В факториальной же системе каждый «разряд» меньше либо равен основанию факториала, перед которым он стоит. При этом действуют обычные для сложения правила переноса разряда при переполнении.
Более математически строго: каждое натуральное число n можно единственным образом представить в виде следующей суммы:
где
km <= m – коэффициент при m! — он же разряд числа в его факториальном представлении,
p – количество «разрядов» в числе в его факториальном представлении
то есть число записывается как kp kp-1 kp-2… k2 k1
Теперь опишем, как использовать факториальное представление (разложение) числа для генерации соответствующей перестановки.
Расположим n элементов в порядке возрастания индекса от 1 до n. Для каждого числа в диапазоне 0..n!-1 произведем факториальное разложение, вычислив его коэффициенты k m. В разложении нуля коэффициенты km будут все нули, в разложении числа n!-1 все km = m, m меняется в диапазоне от 0 до n-1. Теперь поместим элемент с номером m на место с номером km+1, считая лишь свободные места, оставшиеся к этому шагу. Фактически, эта процедура повторяет рассуждения, которые приводятся при вычислении числа возможных перестановок из n элементов – первый элемент может быть размещен n способами, второй – (n-1) способом и так далее. Таким образом, мы получим все возможные перестановки из n несовпадающих элементов.
Проиллюстрируем это для 5 предметов (120 вариантов перестановок) и перестановки №77
77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!
Не являясь программистом-практиком, я все же выскажу предположения (теоретические)), как можно было бы использовать подобное разложение.
Перестановки. Правило умножения. Факториалы презентация, доклад
Перестановки.
Правило умножения.
Факториалы.
Перестановкой называется множество из n элементов, записанных в определённом порядке.
Теорема о перестановках элементов конечного множества
n различных элементов можно расставить
по одному на n различных мест ровно
n! способами.
Рn=n!
Правило умножения: Пусть объект А выбирается mm способами, объект В выбирается nn способами, то оба объекта можно выбрать mnmn способами.
Все очень просто – каждый из mm способов выбора объекта А комбинируется с каждым из nn способов выбора объекта В, то есть количество способов просто умножается друг на друга.
Задача 1
Государственные флаги многих стран состоят из горизонтальных или вертикальных полос разных цветов. Сколько могло бы быть различных государственных флагов, состоящих из двух горизонтальных полос одинаковой ширины и разного цвета – белого, красного и синего?
Решение.
Ответ: 6 флагов
Способ решения — перебор всевозможных вариантов
Верхняя полоса
Нижняя полоса
Флаг
Задача 2.
Из цифр 1, 2, 3, 4 необходимо составить шифр в виде трёхзначного числа так, чтобы каждая цифра встречалась только один раз. Сколькими способами можно составить такой шифр?
Решение.
Полученная схема — дерево возможных вариантов или древо графов
1
2
2
3
4
1
4
1
2
4
1
2
3
3
4
2
1
3
1
3
2
4
2
3
3
4
1
4
1
3
2
4
1
2
1
2
4
3
4
123, 124, 132, 134, 142, 143, 213, 214, 231, 234, 241, 243, 312, 314, 321, 324, 341, 342, 412, 413, 421, 423, 431, 432.
Второй способ решения.
Первую цифру можно выбрать четырьмя способами. Так как после выбора первой цифры останутся три, то вторую цифру можно выбрать уже тремя способами. Наконец, третью цифру можно выбрать (из оставшихся двух) двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению
комбинаторное правило умножения
Пусть имеется п элементов и требуется выбрать из них один за другим k элементов. Если первый элемент можно выбрать п1 способами, после чего второй элемент можно выбрать п2 способами из оставшихся, затем третий элемент можно выбрать п3 способами из оставшихся и т. д., то число способов, которыми могут быть выбраны все k элементов, равно произведению п1 • п2 • п3 • … • nk.
Собрание для проведения тайного голосования во важному вопросу избрало счетную комиссию, в состав которой вошли Антонов, Борисова и Ващенко. Члены счётной комиссии должны распределить обязанности: председатель, заместитель, секретарь.
Сколькими способами они могут это сделать?
Председатель
Заместитель
Секретарь
комиссия
А
Полученная
комбинация
АБВ
АВБ
БАВ
БВА
ВАБ
ВБА
Б
В
Б
В
А
В
А
Б
В
Б
В
А
Б
А
Скачать презентацию
Математический обзор перестановок и факториалов
Математический обзор перестановок и факториалов https://schooltutoring.com/help/wp-content/themes/movedo/images/empty/thumbnail.jpg 150 150 Дебора Дебора https://secure.gravatar.com/avatar/63fb4ad5c163b8f83de2f54371b9e040?s=96&d=mm&r=g
Обзор:
Перестановки и факториалы — тесно связанные математические понятия. Перестановки относятся к порядку объектов, а факториалы включают все возможные исходы события. Если товары упорядочены определенным образом, факториалы определяют, сколько раз их можно заказать.
Что такое перестановки?
Перестановки — это ранжирование, где порядок имеет значение. Предположим, музыкальный продюсер выбирает порядок песен на компакт-диске, выпущенном новым исполнителем. В каждом треке может быть только одна песня. Если записано 10 песен, есть 10 возможностей для вступительного трека. Так как одна песня уже выбрана, осталось 9ушел на вторую дорожку. Для третьего трека осталось 8 и так далее, пока не останется последняя песня. Способ подсчета количества перестановок: 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 3 628 800.
Что такое факториалы?
Факториалы учитывают все возможные исходы события.
Это умножения, которые начинаются с количества событий, умноженного на количество событий -1 и так далее, пока не останется только 1. В примере, где на одной стороне компакт-диска было 10 песен, 10! (читай факториал 10) равно 10 ∙ 9∙ 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1. Число 0! равно 1, примерно так же, как x 0 равно 1. Это математическое соглашение, упрощающее вычисления.
Что такое комбинации?
Комбинации — это ранжирование, в котором порядок не имеет значения. Например, предположим, что 5 человек выбраны из группы из 10 для участия в комитете. В данном случае неважно, в каком порядке их выбирать, ведь конечный результат одинаков. Выбирается целая группа людей. Если бы порядок имел значение, то это было бы 10 ∙ 9∙ 8 ∙ 7 ∙ 6 = 30 240. Поскольку порядок имеет значение, это будет подмножество 30 240. Сколько групп из 5 содержит одни и те же элементы в любом порядке? На это можно ответить с помощью факториала 5!, который равен 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 120.
30240/120 = 252.
Чем они отличаются?
Предположим, что в забеге участвуют 11 бегунов. В большинстве случаев места не получают все 11 участников, а только первые 3. Есть 11 возможностей для первого места, 10 возможностей для второго места и 9возможности для третьего места, или 990 перестановок в первых 3-х местах. Если бы всем бегунам были предоставлены места, это привело бы к 11! мест или 39 916 800 возможных комбинаций.
Заинтересованы в услугах репетитора по алгебре? Узнайте больше о том, как мы помогаем тысячам студентов каждый учебный год.
SchoolTutoring Academy — это ведущая компания, предоставляющая образовательные услуги для учащихся K-12 и колледжей. Мы предлагаем программы репетиторства для учащихся K-12, классов AP и колледжей. Чтобы узнать больше о том, как мы помогаем родителям и учащимся в Конкорде, штат Нью-Гемпшир, посетите веб-сайт Tutoring in Concord, NH 9.0007
вероятность — Перестановки, комбинаторики, факториалы, экспоненты
$\begingroup$
В настоящее время я работаю над курсом вероятностей, и у меня постоянно возникают проблемы с определением того, когда использовать перестановки, комбинации, факториалы и экспоненты, чтобы рассчитать размер выборки или завершить расчеты.
n.
Факториал: Рассмотрим сценарий, в котором у вас есть три разных конфеты. Конфеты могут быть одинаковыми или отличаться по вкусу/марке/типу. Теперь вы должны раздать это трем детям. Когда вы отдаете свою первую конфету первому ребенку, этой конфеты уже нет. У нас есть конечное число объектов, которые нужно распределить между конечным набором участников. Также обратите внимание, что разное распределение приведет к разным результатам для детей. Это перестановка (порядок имеет значение… какой ребенок получит какую конфету имеет значение), но это также частный случай перестановки, потому что количество членов равно количеству продуктов. У нас есть н! Исходы, когда n детей получат n конфет.
Перестановка: Рассмотрим случай выше, но вместо 3 детей у нас есть 10 детей, из которых мы должны выбрать 3, чтобы дать 3 конфеты. Это тоже перестановка, но более общий случай. Здесь количество членов не равно количеству объектов. У нас есть n!/(n-r)! результаты.
Из примера у нас 10 детей, поэтому n = 10, 3 конфеты, поэтому r = 3. Таким образом, факториал такой же, как перестановка, но когда n = r.
Комбинация: теперь рассмотрим немного другой пример случая 3 выше. Вместо того, чтобы раздавать конфеты, вы должны выбрать три конфеты из ведра, полного конфет. Всего в ведерке может быть около 10 конфет. И вы можете сохранить все 3 из них, которые вы выберете. Теперь не имеет значения, в каком порядке вы выбираете три? Это не так. В подобном сценарии выбор конфеты1, конфеты2, конфеты3 в таком порядке ничем не отличается для вас от выбора конфеты3, конфеты2, конфеты1 (в другом порядке). Так что это случай перестановок, но когда некоторые результаты равны друг другу. Следовательно, общее количество комбинаций r вариантов из n предметов равно n!/r!(n-r)!
Я не обсуждал математику вывода уравнения в деталях. Но этот ответ направлен на то, чтобы дать понимание, которое поможет распознавать шаблоны, когда вам нужно их применять.