Сортировка блинов
Сортировка блинов — это математическая задача сортировки неупорядоченной стопки блинов по размеру, когда лопатку можно вставить в любую точку стопки и перевернуть все блины над ней. Число блинов — это минимальное количество бросков, необходимое для заданного количества блинов. В таком виде проблему впервые обсудил американский геометр Джейкоб Э. Гудман . [1] Вариант задачи касается подгоревших блинов, где у каждого блина есть подгоревшая сторона, и, кроме того, все блины должны оказаться подгоревшей стороной вниз.
Все методы сортировки требуют сравнения пар элементов. Для традиционной задачи сортировки обычно изучается проблема минимизации количества сравнений, необходимых для сортировки списка . В этом случае количество реальных операций, таких как замена двух элементов, не имеет значения. В задачах сортировки блинов, напротив, цель состоит в том, чтобы минимизировать количество операций, где единственными разрешенными операциями являются перестановки элементов некоторого префикса последовательности. Теперь количество сравнений не имеет значения.
Проблемы с блинами [ править ]
Оригинальная задача о блинах [ править ]
минимальное количество переворотов, необходимое для сортировки любой стопки из n блинов, находится между Было показано, что 15/14 н и 18/11 н н н приблизительно 1,07 ( и 1,64 ) , но точное значение не известно. [2]
Простейший алгоритм сортировки блинов выполняет не более 2 n − 3 переворотов. В этом алгоритме, своего рода сортировке выбором , мы выносим наверх самый большой блин, еще не отсортированный, одним переворотом; опустите его в конечное положение еще одним переворотом; и повторите этот процесс для остальных блинов.
в 1979 году. Билл Гейтс и Христос Пападимитриу [3] дал нижнюю границу 17/16 ) n n (приблизительно 1,06 переворотов и верхняя граница (5 н +5) / 3 . Верхняя граница была улучшена тридцать лет спустя до 18/11 основателя Хэла группа исследователей из Техасского университета в Далласе под руководством профессора- Садборо . [4] [5]
В 2011 году Лоран Бюльто, Гийом Фертен и Ирена Русу. [6] доказал, что проблема поиска кратчайшей последовательности переворотов для заданной стопки блинов является NP-трудной , тем самым ответив на вопрос, который был открыт более трех десятилетий.
Проблема подгоревших блинов [ править ]
В варианте, называемом задачей о подгоревших блинах , нижняя часть каждого блина в стопке подгорает, и сортировку необходимо завершить сгоревшей стороной каждого блина вниз. Это знаковая перестановка , и если блин i ставится отрицательный элемент i` «сгорел стороной вверх», вместо i в перестановке . В 2008 году группа студентов создала бактериальный компьютер , который может решить простой пример проблемы с подгоревшими блинами, запрограммировав E. coli на переворачивание сегментов ДНК, аналогичных подгоревшим блинам. ДНК имеет ориентацию (5' и 3') и порядок (промотор перед кодированием). Несмотря на то, что вычислительная мощность, выраженная переворотами ДНК, невелика, большое количество бактерий в культуре обеспечивает большую параллельную вычислительную платформу. Бактерии сообщают, что решили проблему, став устойчивыми к антибиотикам. [7]
Проблема блинов со строками [ править ]
Обсуждение выше предполагает, что каждый блин уникален, то есть последовательность, в которой выполняются перестановки префиксов, является перестановкой . Однако «строки» — это последовательности, в которых символ может повторяться, и это повторение может уменьшить количество перестановок префикса, необходимых для сортировки. Читтури и Садборо (2010) и Хуркенс и др. (2007) независимо показали, что сложность преобразования одной совместимой строки в другую с минимальным количеством перестановок префикса является NP-полной . Они также дали пределы для того же самого. Хюркенс и др. дал точный алгоритм сортировки двоичных и троичных строк. Читтури [8] (2011) доказали, что сложность преобразования одной совместимой строки со знаком в другую с минимальным количеством перестановок знакового префикса (проблема сгоревшего блина для строк) является NP-полной.
История [ править ]
Задача о сортировке блинов была впервые поставлена Джейкобом Э. Гудманом , писавшим под псевдонимом «Гарри Дуэйтер» («изнуренный официант»). [9]
Хотя сортировка блинов чаще рассматривается как образовательный инструмент, она также используется в приложениях в параллельных процессорных сетях, где она может обеспечить эффективный алгоритм маршрутизации между процессорами. [10] [11]
Эта проблема примечательна тем, что является темой единственной известной математической статьи Microsoft основателя Билла Гейтса (как Уильям Гейтс) под названием «Границы сортировки по изменению префикса», написанной в соавторстве с Христосом Пападимитриу . Опубликованный в 1979 году, он описывает эффективный алгоритм сортировки блинов. [3] Кроме того, наиболее известная статья, опубликованная «Футурамы» соавтором Дэвидом X. Коэном (как Дэвид С. Коэн), написанная в соавторстве с Мануэлем Блюмом , касалась проблемы подгоревших блинов. [12]
Связанные проблемы знаковой сортировки разворотами и сортировки разворотами изучались и совсем недавно. Хотя для знаковой сортировки обращением найдены эффективные точные алгоритмы, [13] Доказано, что проблему сортировки перестановками трудно даже приблизить с точностью до определенного постоянного коэффициента, [14] а также оказалась аппроксимируемой за полиномиальное время с точностью до коэффициента аппроксимации 1,375. [15]
Блинные графики [ править ]
n - блинный граф — это граф, вершинами которого являются перестановки n символов от 1 до n , а его ребра заданы между перестановками, транзитивными перестановками префиксов. Это регулярный граф с n! вершин, его степень равна n−1. Задача сортировки блинов и задача получения диаметра графа блинов эквивалентны. [16]
Блинный граф размерности n , Pn может быть построен рекурсивно из n копий Pn −1 , присваивая каждой копии другой элемент из набора {1, 2, …, n} в качестве суффикса.
Их обхват :
- .
Поскольку блин-графы обладают многими интересными свойствами, такими как симметричная и рекурсивная структура, малые степени и диаметры по сравнению с размером графа, им уделяется большое внимание как модели сетей взаимосвязей для параллельных компьютеров. [18] [19] [20] Когда мы рассматриваем блинные графы как модель взаимосвязанных сетей, диаметр графа является мерой, отражающей задержку связи. [21] [22]
Блинные графы являются графами Кэли (поэтому они вершинно-транзитивны ) и особенно привлекательны для параллельной обработки. Они имеют сублогарифмическую степень и диаметр и относительно редки (по сравнению, например, с гиперкубами ). [17]
Алгоритм [ править ]
Ниже приведен пример алгоритма сортировки блинов на Python . Код аналогичен пузырьковой сортировке или сортировке выбором .
def flip(arr, k: int) -> None:
left = 0
while left < k:
arr[left], arr[k] = arr[k], arr[left]
k -= 1
left += 1
def max_index(arr, k: int) -> int:
index = 0
for i in range(k):
if arr[i] > arr[index]:
index = i
return index
def pancake_sort(arr) -> None:
n = len(arr)
while n > 1:
maxdex = max_index(arr, n)
if maxdex != n - 1:
if maxdex != 0:
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 7046321 40309555 184992275 639783475 1525125357 2183056566 1458653648 186874852 2001
Последовательности из Интернет-энциклопедии целочисленных последовательностей :
- OEIS : A058986 – максимальное количество переворотов.
- OEIS : A067607 – количество стопок, требующих максимального количества переворотов (выше)
- OEIS : A078941 – максимальное количество переворотов для «сгоревшего» стека.
- OEIS : A078942 — количество переворотов для отсортированной стопки «сгоревшей стороной вверх».
- OEIS : A092113 – треугольник выше, читается по рядам.
Ссылки [ править ]
- ^ Сингх, Саймон (14 ноября 2013 г.). «Переворачивание блинов с математикой» . Хранитель . Проверено 25 марта 2014 г.
- ^ Фертин, Г.; Лабарр, А.; Русский, И.; Танньер, Э.; Виалетт, С. (2009). Комбинаторика перестроек генома . Массачусетский технологический институт Пресс. ISBN 9780262062824 .
- ^ Jump up to: Перейти обратно: а б Гейтс, В .; Пападимитриу, К. (1979). «Границы сортировки по изменению префикса» . Дискретная математика . 27 : 47–57. дои : 10.1016/0012-365X(79)90068-2 .
- ^ «Команда победила молодого Билла Гейтса, предложив улучшенный ответ на так называемую блинную задачу по математике» . Техасский университет в Центре новостей Далласа. 17 сентября 2008. Архивировано из оригинала 14 февраля 2012 года . Проверено 10 ноября 2008 г.
Команда студентов-компьютерщиков UT Далласа и их научный руководитель улучшили давнее решение математической загадки, известной как проблема блинов. Предыдущее лучшее решение, просуществовавшее почти 30 лет, было разработано Биллом Гейтсом и одним из его преподавателей в Гарварде Кристосом Пападимитриу за несколько лет до основания Microsoft.
- ^ Читтури, Б.; Фале, В.; Мэн, З.; Моралес, Л.; Шилдс, Колорадо; Садборо, Айдахо; Войт, В. (31 августа 2009 г.). «Верхняя граница (18/11)n для сортировки по перестановкам префиксов» . Теоретическая информатика . Графики, игры и вычисления: посвящается профессору Буркхарду Моньену по случаю его 65-летия. 410 (36): 3372–3390. дои : 10.1016/j.tcs.2008.04.045 .
- ^ Бюльто, Лоран; Фертен, Гийом; Русу, Ирена (2015). «Переворачивать блины сложно». Журнал компьютерных и системных наук . 81 (8): 1556–1574. arXiv : 1111.0434 . дои : 10.1016/j.jcss.2015.02.003 .
- ^ Хейнс, Кармелла А; Бродерик, Мэриан Л; Браун, Адам Д.; Батнер, Тревор Л; Диксон, Джеймс О; Харден, В. Лэнс; Слышал, Лейн Х; Джессен, Эрик Л; Маллой, Келли Дж; Огден, Брэд Дж; Роузмонд, Сабрия; Симпсон, Саманта; Цвак, Эрин; Кэмпбелл, Малькольм; Экдал, Тодд Т; Хейер, Лори Дж ; Поэт, Джеффри Л. (2008). «Инженерные бактерии для решения проблемы подгоревших блинов» . Журнал биологической инженерии . 2 :8. дои : 10.1186/1754-1611-2-8 . ПМК 2427008 . ПМИД 18492232 .
- ^ Читтури, Бхадрачалам (2011). «Заметка о сложности генетических мутаций». Дискретная математика, алгоритмы и приложения . 03 (3): 269–286. дои : 10.1142/S1793830911001206 .
- ^ Дуэутер, Гарри (1975), «Элементарная задача E2569», Amer. Математика. Ежемесячно , 82 (10): 1009–1010, doi : 10.2307/2318260 , JSTOR 2318260.
- ^ Гаргано, Л.; Ваккаро, У.; Возелла, А. (1993). «Отказоустойчивая маршрутизация в сетях звездного и блинного типа». Письма об обработке информации . 45 (6): 315–320. CiteSeerX 10.1.1.35.9056 . дои : 10.1016/0020-0190(93)90043-9 . МР 1216942 . .
- ^ Канеко, К.; Пэн, С. (2006). «Маршрутизация непересекающихся путей в блинных графах». Материалы седьмой международной конференции по параллельным и распределенным вычислениям, приложениям и технологиям, 2006 г. (PDCAT '06) . стр. 254–259. дои : 10.1109/PDCAT.2006.56 . ISBN 978-0-7695-2736-9 . S2CID 18777751 . .
- ^ Коэн, Д.С .; Блюм, М. (1995). «К вопросу о сортировке подгоревших блинов» . Дискретная прикладная математика . 61 (2): 105. дои : 10.1016/0166-218X(94)00009-3 .
- ^ Каплан, Х.; Шамир, Р.; Тарьян, Р.Э. (1997). «Более быстрый и простой алгоритм сортировки знаковых перестановок путем разворота». Учеб. 8-й ACM-SIAM SODA : 178–87.
- ^ Берман, П.; Карпински, М. (1999). «О некоторых более точных результатах неаппроксимируемости» . Учеб. 26-я ICALP (1999) . Конспекты лекций по информатике. 1644 : 200–09.
- ^ Берман, П.; Карпински, М .; Ханненхалли, С. (2002). «Алгоритмы аппроксимации 1.375 для сортировки разворотами» . Учеб. 10-я ЕКА (2002 г.) . Конспекты лекций по информатике. 2461 : 200–10.
- ^ Асаи, Сёго; Куноике, Юсуке; Синано, Юджи; Канеко, Кейичи (2006). «Вычисление диаметра 17-блинного графа с использованием кластера ПК». В Нагеле, Вольфганг Э.; Вальтер, Вольфганг В.; Ленер, Вольфганг (ред.). Euro-Par 2006, Параллельная обработка, 12-я Международная конференция Euro-Par, Дрезден, Германия, 28 августа – 1 сентября 2006 г., Материалы . Конспекты лекций по информатике. Том. 4128. Спрингер. стр. 1114–1124. дои : 10.1007/11823285_117 .
- ^ Jump up to: Перейти обратно: а б Нгуен, Куан; Беттаеб, Саид (5 ноября 2009 г.). «О роде блинной сети» (PDF) . Международный арабский журнал информационных технологий . 8 (3): 289–292.
- ^ Акл, С.Г.; Цю, К.; Стойменович, И. (1993). «Фундаментальные алгоритмы для звездных и блинчатых сетей с приложениями к вычислительной геометрии». Сети . 23 (4): 215–225. CiteSeerX 10.1.1.363.4949 . дои : 10.1002/net.3230230403 .
- ^ Бас, Д.В.; Садборо, Айдахо (март 2003 г.). «Блинные проблемы с ограниченными перестановками префиксов и некоторыми соответствующими сетями Кэли». Журнал параллельных и распределенных вычислений . 63 (3): 327–336. CiteSeerX 10.1.1.27.7009 . дои : 10.1016/S0743-7315(03)00033-9 .
- ^ Бертоме, П.; Феррейра, А.; Переннес, С. (декабрь 1996 г.). «Оптимальное распространение информации в звездных и блинных сетях». Транзакции IEEE в параллельных и распределенных системах . 7 (12): 1292–1300. CiteSeerX 10.1.1.44.6681 . дои : 10.1109/71.553290 .
- ^ Кумар, В.; Грама, А.; Гупта, А.; Карипис, Г. (1994). Введение в параллельные вычисления: проектирование и анализ алгоритмов . Бенджамин/Каммингс.
- ^ Куинн, MJ (1994). Параллельные вычисления: теория и практика (второе изд.). МакГроу-Хилл.
Дальнейшее чтение [ править ]
- Читтури, Б.; Садборо, Х. (2010). «Перестановка префиксов в строках» . Материалы международной конференции по биоинформатике и вычислительной биологии . 2 : 591–598.
- Читтури, Б. (2011). «Заметка о сложности генетических мутаций». Дискретная математика. Алгоритм. Приложение . 3 (3): 269–287. дои : 10.1142/S1793830911001206 .
- Хейдари, Миннесота; Садборо, Айдахо (1997). «О диаметре блинной сети». Журнал алгоритмов . 25 (1): 67–94. дои : 10.1006/jagm.1997.0874 .
- Херкенс, К.; ван Иерсель, Л.; Кейспер, Дж.; Келк, С.; Стуги, Л.; Тромп, Дж. (2007). «Перестановка префиксов в двоичных и троичных строках». SIAM Journal по дискретной математике . 21 (3): 592–611. arXiv : math/0602456 . дои : 10.1137/060664252 .
- Рони-Дугал, К. ; Ваттер, В. (март 2010 г.). «О блинах, мышах и людях» . Плюс журнал . 54 .
Внешние ссылки [ править ]
- Cut-the-Knot: головоломка с блинами , включая Java-апплет для решения задачи о блинах и некоторое обсуждение.
- Дуглас Б. Уэст «Блинные проблемы»
- Вайсштейн, Эрик В. «Сортировка блинов» . Математический мир .