🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Внезапно, панкейки 🥞
Допустим, у нас есть набор последовательных натуральных чисел, расставленных в произвольном порядке.
Такие последовательности называются перестановками, и для каждой выбранной длины n их количество будет составлять ровно n!
Например, перестановки длины 3 будут выглядеть так:
123, 132, 213, 231, 312, 321.
Их количество равно 3! = 1•2•3 = 6
Введем операцию "флип", смысл которой можно описать так:
"Возьми первые k чисел в перестановке и расставь в обратном порядке". Для краткости будем обозначать ее Rk (reverse k).
Например,
123 -> R2 -> 213
123 -> R3 -> 321
Назовем упорядоченной перестановку, в которой числа расставлены в порядке возрастания.
Сможем ли мы построить последовательность флипов, переводящую произвольную перестановку в упорядоченную?
Спойлер: да, и этот алгоритм несложно придумать. Рекомендую попробовать.
Эта задача называется блинной сортировкой (pancake sorting). И алгоритм построения самой короткой последовательности флипов человечеству неизвестен по сей день.
