Войти
Демонстрация основной операции. Лопатка переворачивает три верхних блина, и результат показан ниже. В задаче о подгоревших блинах теперь будут обожжены их верхние стороны, а не нижние. Сортировка блинов - это математическая задача сортировки неупорядоченной стопки блинов по размеру, когда лопатку можно вставить в любую точку стопки и использовать для переворачивания всех блинов над ней. Номер блина минимальное количество перестроек, необходимых для заданного числа блинов. В таком виде проблема впервые была обсуждена американским геометром Джейкобом Гудманом. Вариант проблемы касается подгоревших блинов, где у каждого блина есть подгоревшая сторона, а все блины, кроме того, должны иметь подгоревшую сторону.
Все методы сортировки требуют сравнения пар элементов. Для традиционной задачи сортировки обычно изучается задача минимизировать количество сравнений, необходимых для сортировки списка. Количество фактических операций, таких как замена двух элементов, не имеет значения. Для задач сортировки блинов, напротив, цель состоит в том, чтобы свести к минимуму количество операций, где единственными разрешенными операциями являются переворачивание элементов некоторого префикса последовательности. Теперь количество сравнений не имеет значения.
Было показано, что минимальное количество переворотов, необходимое для сортировки стопки из n блинов, находится между 15/14п и18/11n (приблизительно 1,07 n и 1,64 n,), но точное значение неизвестно.
Сортировочный простейший блин выполняет алгоритм в большинстве 2 п - 3 переворачивается. В этом алгоритме, своего рода сортировке по выбору, мы одним щелчком переносим наверх самый крупный еще не отсортированный блин; опустите его в конечное положение еще одним переворотом; и повторите этот процесс для оставшихся блинов.
В 1979 году Билл Гейтс и Христос Пападимитриу дали нижнюю границу в 1,06 миллиарда бросков, а верхнюю - в(5 п +5)/3. Тридцать лет спустя верхняя граница была улучшена до 18/11n группой исследователей Техасского университета в Далласе под руководством профессора-основателя Хэла Садборо.
В 2011 году Лоран Булто, Гийом Фертин и Ирена Русу доказали, что задача поиска кратчайшей последовательности переворотов для заданной стопки блинов является NP-сложной, тем самым ответив на вопрос, который оставался открытым более трех десятилетий.
В варианте, который называется проблемой подгоревших блинов, дно каждого блина в куче обожжено, и сортировка должна завершаться так, чтобы подгоревшая сторона каждого блина была опущена вниз. Это перестановка со знаком, и если блин i "подгорел вверх", то вместо i в перестановке помещается отрицательный элемент i`. В 2008 году группа студентов создала бактериальный компьютер, который может решить простой пример проблемы сгоревших блинов, запрограммировав E. coli переворачивать сегменты ДНК, аналогичные сожженным блинам. ДНК имеет ориентацию (5 'и 3') и порядок (промотор перед кодированием). Несмотря на то, что вычислительная мощность, выражаемая с помощью переворотов ДНК, невысока, большое количество бактерий в культуре обеспечивает большую платформу для параллельных вычислений. Бактерии сообщают, когда они решили проблему, став устойчивыми к антибиотикам.
Это навеяно тем, как готовят индийский хлеб ( роти или чапати ). Первоначально все роти складываются в одну колонку, и повар переворачивает роти лопаткой так, чтобы каждая сторона каждого роти в какой-то момент касалась основного огня, чтобы поджарить. Возможны несколько вариантов: гриль можно рассматривать как односторонний или двухсторонний, и может быть запрещено или не поджаривать одну и ту же сторону дважды. Эта версия проблемы была впервые исследована Аркой Ройчоудхури.
Вышеупомянутое обсуждение предполагает, что каждый блин уникален, то есть последовательность, в которой выполняются перестановки префиксов, является перестановкой. Однако «строки» - это последовательности, в которых может повторяться символ, и это повторение может уменьшить количество обращений префикса, необходимых для сортировки. Читтури и Садборо (2010) и Hurkens et al. (2007) независимо показали, что сложность преобразования одной совместимой строки в другую с минимальным числом обращений префикса является NP-полной. Они также дали границы для того же самого. Hurkens et al. дал точный алгоритм сортировки двоичных и троичных строк. Chitturi (2011) доказал, что сложность преобразования совместимой строки со знаком в другую с минимальным числом обращений префикса со знаком - проблема сгоревшего блина на строках - является NP-полной.
Проблема сортировки блинов была впервые поставлена Джейкобом Э. Гудманом, написавшим под псевдонимом «Гарри Двайтер» («взволнованный официант»).
Хотя сортировка блинов чаще рассматривается как обучающее устройство, она также появляется в приложениях в сетях с параллельными процессорами, в которых она может обеспечить эффективный алгоритм маршрутизации между процессорами.
Проблема известна как тема единственной известной математической статьи основателя Microsoft Билла Гейтса (как Уильям Гейтс), озаглавленной «Границы для сортировки по обращению префикса». Опубликованный в 1979 году, он описывает эффективный алгоритм сортировки блинов. Кроме того, наиболее заметная статья, опубликованная одним из создателей Futurama Дэвидом X. Коэном (как Дэвид С. Коэн), касалась проблемы сгоревших блинов. Их сотрудниками были Христос Пападимитриу (тогда в Гарварде, теперь в Колумбии ) и Мануэль Блюм (затем в Беркли, теперь в Университете Карнеги-Меллона ) соответственно.
Связанные проблемы знаковой сортировки обращениями и сортировки обращениями также изучались совсем недавно. В то время как эффективные точные алгоритмы были найдены для знаковой сортировки по разворотам, проблема сортировки по разворотам оказалась трудной даже для аппроксимации с точностью до определенного постоянного множителя, а также доказана возможность аппроксимации за полиномиальное время с точностью до коэффициента аппроксимации 1,375..
Блинный график П 3 
Блинный граф P 4 может быть построен рекурсивно из 4 копий P 3, назначая другой элемент из набора {1, 2, 3, 4} в качестве суффикса для каждой копии. Основная статья: Блинный график П -pancake графа представляет собой график, вершины которого являются перестановками п символов от 1 до п и его ребро приведено между перестановками транзитивны с помощью префикса инверсий. Это обычный граф с n! вершин, его степень n - 1. Задача сортировки блинов и задача получения диаметра графа блинов эквивалентны.
Блинный граф размерности n, P n может быть построен рекурсивно из n копий P n − 1, назначая другой элемент из набора {1, 2,…, n} в качестве суффикса для каждой копии.
Их обхват :
Γ (Р п) род Р п является:
Поскольку графы-блины обладают множеством интересных свойств, таких как симметричные и рекурсивные структуры, малые степени и диаметры по сравнению с размером графа, им уделяется большое внимание как модели сетей взаимосвязей для параллельных компьютеров. Когда мы рассматриваем блинные графы как модель взаимосвязанных сетей, диаметр графа является мерой, которая представляет задержку связи.
Графы-блины - это графы Кэли (поэтому они транзитивны по вершинам ) и особенно привлекательны для параллельной обработки. Они имеют сублогарифмическую степень и диаметр и относительно редки (по сравнению, например, с гиперкубами ).
Пример алгоритма сортировки блинов на Python приведен ниже.
def flip(arr, k): left = 0 while left lt; k: arr[left], arr[k] = arr[k], arr[left] k -= 1 left += 1 def max_index(arr, k): index = 0 for i in range(k): if arr[i] gt; arr[index]: index = i return index def pancake_sort(arr): n = len(arr) while n gt; 1: maxdex = max_index(arr, n) flip(arr, maxdex) flip(arr, n - 1) n -= 1 arreglo = [15, 8, 9, 1, 78, 30, 69, 4, 10] pancake_sort(arreglo) print(arreglo)
| Высота n | k | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 1 | 1 | |||||||||||||||
| 2 | 1 | 1 | ||||||||||||||
| 3 | 1 | 2 | 2 | 1 | ||||||||||||
| 4 | 1 | 3 | 6 | 11 | 3 | |||||||||||
| 5 | 1 | 4 | 12 | 35 год | 48 | 20 | ||||||||||
| 6 | 1 | 5 | 20 | 79 | 199 | 281 | 133 | 2 | ||||||||
| 7 | 1 | 6 | 30 | 149 | 543 | 1357 | 1903 г. | 1016 | 35 год | |||||||
| 8 | 1 | 7 | 42 | 251 | 1191 | 4281 | 10561 | 15011 | 8520 | 455 | ||||||
| 9 | 1 | 8 | 56 | 391 | 2278 | 10666 | 38015 | 93585 | 132697 | 79379 | 5804 | |||||
| 10 | 1 | 9 | 72 | 575 | 3963 | 22825 | 106461 | 377863 | 919365 | 1309756 | 814678 | 73232 | ||||
| 11 | 1 | 10 | 90 | 809 | 6429 | 43891 | 252737 | 1174766 | 4126515 | 9981073 | 14250471 | 9123648 | 956354 | 6 | ||
| 12 | 1 | 11 | 110 | 1099 | 9883 | 77937 | 533397 | 3064788 | 14141929 | 49337252 | 118420043 | 169332213 | 111050066 | 13032704 | 167 | |
| 13 | 1 | 12 | 132 | 1451 | 14556 | 130096 | 1030505 | 7046318 | 40309555 | 184992275 | 639783475 | 1525125357 | 2183056566 | 1458653648 | 186874852 | 2001 г. |
Последовательности из Интернет-энциклопедии целочисленных последовательностей :
.