Berloga - науки и технологии

Внезапно, панкейки 🥞 Допустим, у нас есть набор последовательных натуральных чисел, расставленных в произвольном порядке. Такие последовательности называются перестановками, и для каждой выбранной длины 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). И алгоритм построения самой короткой последовательности флипов человечеству неизвестен по сей день.