No quiero el más pequeño, quiero el segundo más pequeño

Question

Inspirado por mis luchas con el sistema de calificación de una determinada plataforma de aprendizaje en línea de código abierto:

Está trabajando en un lenguaje informático con un conjunto limitado de funciones integradas. Tienes un conjunto de$m$ numeros reales $x_1, x_2, \dots x_m$. Estos números están en algún orden arbitrario y desconocido (es decir, no necesariamente aumentan o disminuyen monótonamente).

Desea escribir una función que devuelva el "segundo más pequeño" de estos números, donde las entradas duplicadas se tratan como distintas. En otras palabras, si tuviéramos que enumerar los números de menor a mayor, esta función devolvería el segundo número en esa lista ordenada. Por ejemplo, si los números son$\{ 2, 6, 1, 7\}$, la función debería regresar $2$. Si los números son$\{ 4, 5, 4, 4, 4, 5 \}$, la función debería regresar $4$.

Las funciones que puede utilizar son:

• max(x1, x2, ...)y min(x1, x2, ...): Acepta cualquier número de argumentos de números reales. Devuelve el más grande o el más pequeño, respectivamente.
• sum(x1, x2, ...): Acepta cualquier número de argumentos de números reales. Devuelve la suma de todos ellos.

Además, puede utilizar las operaciones aritméticas estándar +, -, *, /, y ^.

PREGUNTA EXTRA:

Amplíe su método para devolver el $n$el número más pequeño del conjunto.

Mis respuestas destinadas para ambas preguntas sólo utilizan max, sumy las operaciones aritméticas. Sin embargo, si puede encontrar una respuesta más elegante que utilice otras funciones integradas en esta lista, también me interesaría. :-)

Answer 1

Lo mejor que puedo pensar es esto:

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

es decir

Hallar la suma mínima de dos números, luego restarla con el más pequeño.

Entonces para el $n$-th más pequeño:

Trate de encontrar la suma mínima de $n$ números, luego réstelo con la suma mínima de $n-1$ números.

Answer 2

Tal vez no lo entiendo (quiero decir, es una solución, simplemente no sé si está permitido), pero:

$max(min(set_1)min(set_2)…min(set_m))$ donde cada $set_k$ contiene todos los números, excepto $x_k$ (y el número de conjuntos es igual a $(m)$ )

y para $3$rd menor número sería similar

solo cada "conjunto" contendría todos los números excepto dos, y cada combinación de eso, por lo que el número de conjuntos sería algo así como $(m)$X$(m-1)/2$.

y para $4$el número más pequeño sería similar

solo cada "conjunto" contendría todos los números excepto tres, y cada combinación de eso, por lo que el número de conjuntos sería algo así como $(m)$X$(m-1)$X$(m-2)/(3!)$.
¡Dividido por 3! porque solo tomo una combinación de ciertos$x_i$, $x_j$, $x_k$e ignorando ($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$).

y así

Answer 3

Esta solución se inspiró originalmente en la solución de athin , pero con una forma mejorada de generar la suma de los dos números más pequeños. Ahora, es una variante de la solución de Bass ya que, como sugirieron en los comentarios, podemos cambiar la suma a un máximo, y luego no es necesario restar el número más pequeño al final.

Indexemos las entradas como $x_0, x_1, \dots, x_{m-1}$. Escribe los números$0, 1, \dots, m-1$en binario. Para cada$k=1,2,\dots,\lceil\log_2 m\rceil$, dejar $A_k$ ser el min de todos $x_i$ tal que $i$ tiene un $0$ en el $k$-ésima posición; dejar$B_k$ ser el min de todos $x_i$ tal que $i$ tiene un $1$ en el $k$-ésima posición. Entonces nuestra solución es$$\min(\max(A_1,B_1),\max(A_2,B_2),\dots,\max(A_k,B_k)).$$ El número de $x$en esta expresión es $m \lceil \log_2 m \rceil$.

He aquí por qué funciona esto:

Cada $\max(A_k,B_k)$será el máximo de dos elementos, por lo que es al menos el segundo elemento más pequeño. Por otro lado, si$x_i$ y $x_j$ son los dos mas pequeños $x$s, entonces tiene que haber alguna posición $k$ donde las representaciones binarias de $i$ y $j$diferir de; decir,$i$ tiene un $0$ en el $k$-ésima posición, y $j$ tiene un $1$. Entonces tendremos$A_k = x_i$ y $B_k = x_j$, entonces $\max(A_k,B_k) = \max(x_i,x_j)$definitivamente aparecerá en el minuto que tomemos. Ninguna otra$\max(A_{k'}, B_{k'})$ puede ser más pequeño, entonces $\max(x_i,x_j)$, el segundo elemento más pequeño, es nuestra respuesta final.

Aquí hay un ejemplo de la fórmula terminada para $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).$$

Y aquí hay un diagrama de esa solución dibujado por humn :

---

Podemos generalizar esto a un $O(m \log m)$ solución para encontrar el $k^{\text{th}}$elemento más pequeño, confiando en una respuesta Math.SE escrita hace un año por un individuo inteligente y guapo.

Digo "algo así" porque esto es solo una construcción aleatoria. No en el sentido de que funcione solo en algunas entradas aleatorias. Es aleatorio en el sentido de que describiré un método para generar una fórmula con cierta aleatoriedad en el método; con probabilidad positiva, nos dará una fórmula que siempre funciona para todas las entradas.

Así es cómo.

Una "cláusula" en nuestra fórmula se parece a lo siguiente. Nos separamos$\{1,2,\dots,m\}$ dentro $k$ conjuntos $S_1, S_2, \dots, S_k$y luego tomar $$\max\{\min\{x_i : i \in S_1\}, \min\{x_i : i \in S_2\}, \dots, \min\{x_i : i \in S_k\}\}.$$ El valor que esto genera es siempre un máximo de $k$elementos distintos, por lo que es al menos el$k^{\text{th}}$pequeñísimo. Y si el$k$ los elementos más pequeños se distribuyen uniformemente entre $S_1, \dots, S_k$, entonces el valor de la cláusula es el$k^{\text{th}}$ elemento más pequeño.

Para asegurarnos de que esto siempre suceda, generamos muchas cláusulas al azar: para cada $i \in \{1,2,\dots,m\}$, elegimos (de forma independiente y uniforme al azar) ponerlo en uno de $S_1, \dots, S_k$. Como se muestra en la respuesta Math.SE a la que me vinculé, si generamos$\frac{k^k}{k!} \ln \binom mk \approx k e^k \ln m$cláusulas, entonces con probabilidad positiva será cierto que para cualquier $k$variables, hay una cláusula que las separa. Cuando esto suceda, nuestra fórmula final será el mínimo de todas estas cláusulas.

Answer 4

Aquí hay otro enfoque más. Se encuentra entre los métodos de @ athin y @Jan Ivan .

Se basa en la observación de que el segundo número más pequeño es

el número más pequeño que es mayor (o igual a) algún otro número.

Esto significa que podemos hacer

un min () sobre todos los posibles pares max () es: $$\min\left(\max(x_1, x_2), \max(x_1,x_3),\ldots, \max(x_{m-1}, x_m)\right)$$

Para comprobar que esto funciona, solo tenemos que notar que

el número más pequeño que nunca se mostrará como una de las max () es, a menos que haya un empate por el más pequeño, que es exactamente el caso especial en que hacer queremos que se presentó.