| Порядок | Комбинационное число |
| 0 0 0 0 0 | |
| 0 0 0 1 0 | |
| 0 0 1 0 0 | |
| 0 0 1 1 0 | |
| 0 0 2 0 0 | |
| 0 0 2 1 0 | |
| 0 1 0 0 0 | |
| 0 1 0 1 0 | |
| 0 1 1 0 0 | |
| 0 1 1 1 0 | |
| 0 1 2 0 0 | |
| 0 1 2 1 0 | |
| 0 2 0 0 0 | |
| … | …………. |
| 4 3 1 1 0 | |
| 4 3 2 0 0 | |
| 4 3 2 1 0 |
Пример. Найдем перестановкуиз шести букв A,B,C,D,E,F с порядковым номером 267.
Так как здесь 6 букв,то количество всевозможных перестановок 6! = 720
- Элемент 5 Изменяется в каждом 120 прибавлении порядке.
- Элемент 4 Изменяется в каждом 24 прибавлении порядке.
- Элемент 3 Изменяется в каждом 6 прибавлении порядке.
- Элемент 2 Изменяется в каждом 2 прибавлении порядке.
- Элемент 1 Изменяется в каждом прибавлении.
- Элемент 0 Изменяется в каждом прибавлении.
- Сначала, разделим 267 на 120. Частное будет 2 с остатком 27. Значит, элемент 5 меняется дважды.
- Чтобы найти число изменений элемента 4, мы должны использовать остаток 27 и поделить его на 4! – число изменений каждогоприбавления, т. е., 27 делим на 24. Частное 1, а остаток 3.
- Чтобы найти число изменений элемента 3, используем остаток 3 и поделим его на 3! – число изменений каждого прибавления. Таким образом, выходит 3 деленное на 6. Частное 0 и остаток 3.
- Чтобы найти число изменений элемента 2, остаток 3 делим на 2! – число изменений каждого прибавления. Значит, 3 делим на 2. Частное 1 и остаток 1.
- Чтобы найти элемент 1 нужно использовать остаток 1 и поделить его на 1! – число изменений в каждом прибавлении. 1 делим на 1. Частное будет 1 и остаток 0.
- Чтобы найти элемент 0, используем остаток 0 и поделим его на 0! – число изменений каждом прибавлении. 0 делим на 1. Частное будет 0 и остаток 0.
Теперь, перечислим частные, и это будет комбинационным числом:
Как по комбинационному числу найти перестановку?
Рассмотрим перестановки букв А, B, C, D, E, F. Используя комбинационное число 210110, найдем соответствующую перестановку.
Для этого поместим самую первую перестановку A B C D E F в первую строку таблицы, а во вторую строку будем последовательно заполнять элементы искомой перестановки:
| A | B | C | D | E | F |
Так как первое комбинационное число 2, пропускаем две буквы в начальной перестановке и вставляем следующую букву в первую клетку второй строки. (Как видите снизу: C)
| A | B | D | E | F | |
| C |
Так как второе комбинационное число перестановки равно 1, то пропускаем одну букву в начальной перестановке и вставляем следующую букву во вторую клетку второй строки. (Как видите снизу: B).
| A | D | E | F | ||
| C | B |
Так как второе комбинационное число равно 0, не пропускаем ни одного из чисел в начальной перестановке и вставляем первое доступное число в третью клетку второй строки. (Как видите снизу: A)
| D | E | F | |||
| C | B | A |
Так как четвертое комбинационное число равно 1, пропускаем одну букву в начальной перестановке и вставляем следующую букву в четвертую клетку. (Как видите снизу: E).
| D | F | ||||
| C | B | A | E |
Так как пятоге комбинационное число равно 1, пропускаем одну букву в начальной перестановке и вставляем следующую букву в пятую клетку. (Как видите снизу: F)
| D | |||||
| C | B | A | E | F |
Так как осталась только одна буква, помещаем её в шестую клетку.
| C | B | A | E | F | D |
C B A E F D.
Таким образом, мы можем по поряковому номеру перестановки определить комбинационное число, затем по комбинационному числу определить перестановку. Как видно, алгоритмы нахождения используют минимальное число операций.
ПОРЯДКОВЫЙ НОМЕР
↓
КОМБИНАЦИОННОЕ ЧИСЛО
↓
ПЕРЕСТАНОВКА
Пример 1: Теперь решим следующую задачу: по порядковому номеру перестановки восстановить саму перестановку.
Для этого нужно:
1) По порядковому номеру перестановки построить комбинационное число (§ 1).
2) По построенному комбинационному числлу построить саму перестановку.(§ 2)
A B C D E F - Нужно найти весь этот порядок комбинаций.
Для того, чтобы найти возможное количество перестановок, нужно найти 6! = 720.
Если А B C D E F – первоначальная комбинация, то какая перестановка для порядкового номера 511?
Из порядкового номера 511 мы можем вычислить перестановку.
(A) Меняется один раз в каждых 120 приращениях порядка.
(B) Меняется один раз в каждых 24 приращениях порядка.
(C) Меняется один раз в каждых 6 приращениях порядка.
(D) Меняется один раз в каждых 2 приращениях порядка.
(E) Меняется в каждом приращении порядка.
(F) Меняется в каждом приращении порядка.
1) 511 делим на 120, частное 4 и остаток 31.
2) Полученный остаток 31 делим на 24, частное 1 и остаток 7.
3) Остаток 7 делим на 6, частное 1, остаток 1.
4) Остаток 1 делим на 2, частное 0, остаток 1.
5) Остаток 1 делим на 1, частное 1, остаток 0.
6) Остаток 0 делим на 1, частное 0, остаток 0.
Комбинационное число = 4 1 1 0 1 0
| A | B | C | D | E | F |
| E | B | C | A | F | D |