Задача о болтах и гайках

[worm2]

Имеется $N$ болтов и столько же гаек, отличающихся диаметрами. Нет ни двух болтов одинакового диаметра, ни двух гаек одинакового диаметра. Однако каждая гайка подходит по диаметру ровно к одному болту, и наоборот.

За одну операцию разрешается сравнить диаметры одного болта и одной гайки. Сравнивать между собой диаметры болтов или диаметры гаек непосредственно нельзя, только опосредованно: например, выяснив, что диаметр болта X больше диаметра гайки Y, а диаметр гайки Y больше диаметра болта Z, мы можем заключить, что диаметр болта X больше диаметра болта Z. "На глазок" тоже ничего не видно

Требуется определить, какому болту какая гайка подходит по диаметру.

Понятно, что можно тупо сравнить каждую гайку с каждым болтом, и дело в шляпе.
Интересует алгоритм, использующий менее, чем $O(N^2)$ операций.

[hurtsy]

worm2 в сообщении #461093 писал(а):

Понятно, что можно тупо сравнить каждую гайку с каждым болтом, и дело в шляпе.
Интересует алгоритм, использующий менее, чем $O(N^2)$ операций.

Для начала все равно берем наугад гайку и меряем со всеми болтами. В результате болты разбиты на большие гайки, меньшие и один того же размера что и гайка. Этим болтом разобьем множество гаек на две группы. В результате получаем две задачи меньшей размерности. Напоминает метод половинного деления. С уважением,

[worm2]

Вероятно, в среднем данный метод приведёт к результату достаточно быстро. Однако в наихудшем случае может случиться так, что взятая наугад гайка окажется самой маленькой или самой большой (или её диаметр будет достаточно близок к экстремальному). И тогда число требуемых сравнений окажется близким к максимальному.

[Praded]

А если болты одинакового диаметра и различаются шагом резьбы, её направлением и/или числом заходов?

[worm2]

А нам всё равно. Главное — диаметр, а там молотком забьём если чо.

[hurtsy]

worm2 в сообщении #461195 писал(а):

И тогда число требуемых сравнений окажется близким к максимальному.

А вероятность такого печального исхода $\frac 1 {N!}$. С уважением,

[venco]

Рабочая структура - множество деревьев, в которых каждый узел (болт или гайка) меньше дочерних узлов. В каждом дереве тип узлов (болт/гайка) чётных и нечётных уровней чередуется. Причём обязательно есть хотя бы одно дерево с болтом в корне, и хотя бы одно дерево с гайкой в корне, т.к. самые маленькие из не подобранных болт и гайка находятся в корне какого-либо дерева.
Изначально у нас N деревьев с гайкой в корне и N деревьев с болтом в корне (без дочерних узлов).
На каждом шаге берём самое маленькое дерево с болтом в корне и самое маленькое дерево с гайкой в корне, и сравниваем эти корни.
Если они подходят, то отделяем их, а соответствующие поддеревья возвращаем в общее множество деревьев. Если не подходят, то объединяем эти деревья соответствующим образом.
В конце концов все пары найдутся. Сложность, вроде, получается $N \log N$.

-- Ср июн 22, 2011 18:53:22 --

Увы, всё равно в худшем случае квадрат.

[Psw]

Все предложенное есть у Д.Кнута - Искусство программирования для ЭВМ, том 3.
Только немного модифицировать надо.
hurtsy предложил метод Быстрой сортировки Хоара, наиболее быстрый в среднем. Но в худшем случае имеет порядок $N^2$
venco - Пирамидальная сортировка, хотя надо разобраться с реализацией - все ли получится. Этот алгоритм и в среднем, и в худшем, да вообще-то всегда имеет время работы порядка $N \ln N $, но очень велики накладные расходы, в несколько раз выше, чем в Быстрой сортировке.

[Sender]

Можно попробовать так: сформируем упорядоченный по возрастанию массив, элементами которого являются неупорядоченные множества элементов одного типа(болтов или гаек) и пары подходящих болтов и гаек. Упорядоченность массива означает, что все болты (гайки) n-го элемента меньше всех гаек (болтов) n+1-го элемента. Сначала формируем пустой массив, затем добавляем в него по очереди болты и гайки из исходного набора, сохраняя упорядоченность по возрастанию: добавляя болт или гайку, ищем место вставки в массив бинарным поиском. Сравнивая, к примеру, болт с элементом, представляющим собой неупорядоченное множество гаек, сравниваем его по очереди со всеми гайками этого множества, если при этом какие-то гайки меньше болта, а какие-то больше, разбиваем этот элемент на два, болт помещаем между ними. Если какая-то гайка подходит к болту, помещаем её в один элемент с ним. В итоге должен получиться упорядоченный массив подходящих пар.

Да, в худшем случае получается $O(N^2)$ опять-таки.

[hurtsy]

Psw в сообщении #461300 писал(а):

hurtsy предложил метод Быстрой сортировки Хоара, наиболее быстрый в среднем. Но в худшем случае имеет порядок $N^2$

Официально заявляю, у меня нет претензий на авторство.
В таких вещах никогда не знаешь откуда информация попала "в подсознание". Но это дествительно болезнь многих практических алгоритмов, обязательно находится случай для худших ожиданий. Если для "бессмертных" алгоритмов это контрпример, для "коротко живущих " программ, зависящих от версий ОС, версий ПО(языка программирования) да иногда от требований заказчика,(к сожалению давно не встречался с таковым), приходится учитывать малую вероятность "контрпримера".
У меня есть подозрение, что у топик стартера заготовлен ответ. Так сообщите, не томите душу.
С уважением,

[worm2]

hurtsy писал(а):

У меня есть подозрение, что у топик стартера заготовлен ответ.

Увы мне, топикстартеру
Я прочитал о задаче пару недель назад вот здесь:
http://easy-coding.blogspot.com/2011/06/blog-post.html
Несколько раз брался за решение, но у меня ничего не получилось.
Но это ещё не значит, что она очень сложная.
Может быть, здесь есть какой-то простой и изящный ход, который при длительном обдумывании всплывёт из подсознания. Тем более, там пишут, что задача задаётся на собеседовании.

[venco]

Попробовал приспособить сортировки вставкой и слиянием. В любом случае получается худший вариант $O(N^2)$. Похоже, это неизбежно.

[hurtsy]

worm2 в сообщении #461373 писал(а):

Тем более, там пишут, что задача задаётся на собеседовании.

Собеседование, необязательно , преследует цель решить задачу. Там диапазон от фильтрации до селекции собеседуемых. Я уж было на Вас понадеялся. С уважением

[Alexu007]

hurtsy в сообщении #461192 писал(а):

Для начала все равно берем наугад гайку и меряем со всеми болтами. В результате болты разбиты на большие гайки, меньшие и один того же размера что и гайка. Этим болтом разобьем множество гаек на две группы. В результате получаем две задачи меньшей размерности. Напоминает метод половинного деления. С уважением,

//модификация метода hurtsy:

Сравниваем две группы рассортированных болтов, если одна сильно превышает другую (первоначальный выбор гайки оказался неудачным) - то найденную пару в ящик готовой продукции и начинаем сначала. Если рассортированные болты поделились примерно поровну, то рассортировываем болтом гайки и продолжаем поиск отдельно в каждой группе.

[hurtsy]

Alexu007 в сообщении #462012 писал(а):

Если рассортированные болты поделились примерно поровну, то рассортировываем болтом гайки и продолжаем поиск отдельно в каждой группе.

А если иначе ... В том то и дело, "сатана никогда не ждет реванша" и опять впереди маловероятное но такое грозное $O(N^2)$.Вот если бы применить метод подобный тому, что если треугольник закрепить в вершине, отвесная линия будет медианой. Остается надежда на быстрые упорядочения.

venco в сообщении #461500 писал(а):

В любом случае получается худший вариант $O(N^2)$. Похоже, это неизбежно.

С уважением,