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

Даны объектов; нужно составить из них все возможные комбинации, переставляя их между собой. Такие комбинации называются перестановками из элементов.

Перестановки отличаются друг от друга только порядком расположения элементов.

Задача о шляпах: перечислить все способы, которыми три человека могут надеть три шляпы. Каждый такой способ можно считать перестановкой из трех шляп или трех чисел 1, 2, 3 (если закодировать шляпы числами): 123, 132, 213, 231, 312, 321.

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

Полученное выражение представляет собой произведение всех натуральных чисел от 1 до . В математике это произведение называется факториалом числа и обозначается (читается «эн факториал»). Заметим, что 1!=1. Интересно, что для удобства (вы оцените его чуть позже) полагают и 0!=1.

Отметим одну важную особенность этой замечательной функции – ее быстрый рост. Приведем для примера несколько значений факториала для возрастающих значений :                                           40 320 362 880 3 628 800 39 916 800 479 001 600

Пример:

Дано слово РОСТ. Нужно получить слова, которые можно получить из него всевозможными перестановками букв. Каждое такое слово будет перестановкой из четырех заданных букв. Всего таких перестановок будет 4!=24.