Я не хочу самый маленький, я хочу второй самый маленький

Aug 20 2020

Вдохновленный моей борьбой с системой оценок определенной платформы онлайн-обучения с открытым исходным кодом:

Вы работаете на компьютерном языке с ограниченным набором встроенных функций. У вас есть набор$m$ вещественные числа $x_1, x_2, \dots x_m$. Эти числа расположены в произвольном неизвестном порядке (т. Е. Они не обязательно монотонно увеличиваются или уменьшаются).

Вы хотите написать функцию, которая возвращает «второе по величине» из этих чисел, где повторяющиеся записи рассматриваются как отдельные. Другими словами, если бы мы перечислили числа от наименьшего к наибольшему, эта функция вернула бы второе число в этом упорядоченном списке. Например, если числа$\{ 2, 6, 1, 7\}$, функция должна вернуть $2$. Если числа$\{ 4, 5, 4, 4, 4, 5 \}$, функция должна вернуть $4$.

Вы можете использовать следующие функции:

max(x1, x2, ...)и min(x1, x2, ...): принимает любое количество аргументов действительного числа. Возвращает наибольшее или наименьшее значение соответственно.
sum(x1, x2, ...): Принимает любое количество аргументов действительного числа. Возвращает их все.

Кроме того, вы можете использовать стандартные арифметические операции +, -, *, /, и ^.

БОНУСНЫЙ ВОПРОС:

Расширьте свой метод, чтобы вернуть $n$-е наименьшее число среди множества.

Мои ответы , предназначенные для обоих вопросов использования только max, sumи арифметические операции. Однако, если вы можете придумать более элегантный ответ, который использует другие встроенные функции из этого списка, он также будет мне интересен. :-)

Ответы

25 athin Aug 20 2020 at 22:48

Лучшее, что я могу придумать, это следующее:

$$min((x_1+x_2),(x_1+x_3),\cdots,(x_{m-1}+x_m)) - min(x_1,x_2,\cdots,x_m)$$

т.е.

Найдите минимальную сумму двух чисел, затем вычтите ее с наименьшим.

Так что для $n$-й наименьший:

Попробуйте найти минимальную сумму $n$ чисел, затем вычтите его с минимальной суммой $n-1$ числа.

17 JanIvan Aug 20 2020 at 21:44

Может, я не понимаю (я имею ввиду, это решение, я просто не знаю, разрешено ли это), но:

$max(min(set_1)min(set_2)…min(set_m))$ где каждый $set_k$ содержит все числа, кроме $x_k$ (а количество комплектов равно $(m)$ )

и для $3$rd наименьшее число было бы похоже

просто каждый «набор» будет содержать все числа, кроме двух - и каждую их комбинацию, поэтому количество наборов будет примерно таким $(m)$Икс$(m-1)/2$.

и для $4$th наименьшее число было бы похоже

просто каждый «набор» будет содержать все числа, кроме трех - и каждую их комбинацию, поэтому количество наборов будет примерно таким $(m)$Икс$(m-1)$Икс$(m-2)/(3!)$.
Делится на 3! потому что я просто беру одну комбинацию определенных$x_i$, $x_j$, $x_k$, и игнорируя ($x_j$, $x_i$, $x_k$), ($x_k$, $x_i$, $x_j$), ($x_j$, $x_k$, $x_i$), ($x_k$, $x_j$, $x_i$), ($x_i$, $x_k$, $x_j$).

и так далее

9 MishaLavrov Aug 21 2020 at 08:25

Первоначально это решение было вдохновлено решением athin , но с улучшенным способом генерации суммы двух наименьших чисел. Теперь это вариант решения Басса, поскольку, как они предложили в комментариях, мы можем изменить сумму на максимум, и тогда нам не нужно вычитать наименьшее число в конце.

Проиндексируем входы как $x_0, x_1, \dots, x_{m-1}$. Запиши номера$0, 1, \dots, m-1$в двоичном формате. Для каждого$k=1,2,\dots,\lceil\log_2 m\rceil$, позволять $A_k$ быть минусом из всех $x_i$ такой, что $i$ имеет $0$ в $k$-я позиция; позволять$B_k$ быть минусом из всех $x_i$ такой, что $i$ имеет $1$ в $k$-я позиция. Тогда наше решение$$\min(\max(A_1,B_1),\max(A_2,B_2),\dots,\max(A_k,B_k)).$$ Номер $x$в этом выражении $m \lceil \log_2 m \rceil$.

Вот почему это работает:

Каждый $\max(A_k,B_k)$будет максимум из двух элементов, поэтому это как минимум второй по величине элемент. С другой стороны, если$x_i$ и $x_j$ два самых маленьких $x$'s, тогда должна быть какая-то позиция $k$ где двоичные представления $i$ и $j$отличаются; сказать,$i$ имеет $0$ в $k$-я позиция, и $j$ имеет $1$. Тогда мы получим$A_k = x_i$ и $B_k = x_j$, так $\max(A_k,B_k) = \max(x_i,x_j)$обязательно появится через минуту, которую мы берем. Нет другого$\max(A_{k'}, B_{k'})$ может быть меньше, поэтому $\max(x_i,x_j)$, второй по величине элемент, и есть наш окончательный ответ.

Вот пример готовой формулы для $m=8$:

$$\min\Big(\max(\min(x_0,x_2,x_4,x_6),\min(x_1,x_3,x_5,x_7)), \max(\min(x_0,x_1,x_4,x_5),\min(x_2,x_3,x_6,x_7)), \max(\min(x_0,x_1,x_2,x_3),\min(x_4,x_5,x_6,x_7))\Big).$$

А вот диаграмма этого решения, нарисованная humn :

Мы можем обобщить это на $O(m \log m)$ решение для поиска $k^{\text{th}}$наименьший элемент, полагаясь на ответ Math.SE, написанный год назад умным и красивым человеком.

Я говорю «вроде как», потому что это всего лишь случайная конструкция. Не в том смысле, что он работает только с некоторыми случайными входами. Это случайность в том смысле, что я опишу метод генерации формулы с некоторой случайностью в методе; с положительной вероятностью это даст нам формулу, которая всегда работает для всех входных данных.