Non voglio il più piccolo, voglio il secondo più piccolo
Ispirato dalle mie difficoltà con il sistema di valutazione di una certa piattaforma di apprendimento online open source:
Stai lavorando in un linguaggio informatico con un insieme limitato di funzioni integrate. Hai una serie di$m$ numeri reali $x_1, x_2, \dots x_m$. Questi numeri sono in un ordine arbitrario e sconosciuto (cioè, non necessariamente aumentano o diminuiscono in modo monotonico).
Si desidera scrivere una funzione che restituisca il "secondo più piccolo" di questi numeri, dove le voci duplicate vengono trattate come distinte. In altre parole, se dovessimo elencare i numeri dal più piccolo al più grande, questa funzione restituirebbe il secondo numero in quella lista ordinata. Ad esempio, se i numeri sono$\{ 2, 6, 1, 7\}$, la funzione dovrebbe tornare $2$. Se i numeri lo sono$\{ 4, 5, 4, 4, 4, 5 \}$, la funzione dovrebbe tornare $4$.
Le funzioni che puoi utilizzare sono:
max(x1, x2, ...)emin(x1, x2, ...): accetta un numero qualsiasi di argomenti in numero reale. Restituisce rispettivamente il più grande o il più piccolo.sum(x1, x2, ...): Accetta un numero qualsiasi di argomenti in numero reale. Restituisce la somma di tutti loro.
Inoltre, è possibile utilizzare le operazioni aritmetiche standard di +, -, *, /, e ^.
DOMANDA BONUS:
Estendi il tuo metodo per restituire il file $n$il numero più piccolo dell'insieme.
Le mie risposte previsti per entrambe le domande usano solo max, sume le operazioni aritmetiche. Tuttavia, se riesci a trovare una risposta più elegante che utilizzi altre funzioni integrate in questo elenco, sarebbe interessante anche per me. :-)
Risposte
Il meglio che posso tirar fuori è questo:
$$min((x_1+x_2),(x_1+x_3),\cdots,(x_{m-1}+x_m)) - min(x_1,x_2,\cdots,x_m)$$
cioè
Trovare la somma minima di due numeri, quindi sottrarla con il più piccolo.
Quindi per il $n$-la più piccola:
Prova a trovare la somma minima di $n$ numeri, quindi sottrarlo con la somma minima di $n-1$ numeri.
Forse non capisco (voglio dire, è una soluzione, solo che non so se è consentito), ma:
$max(min(set_1)min(set_2)…min(set_m))$ dove ciascuno $set_k$ contiene tutti i numeri, tranne $x_k$ (e il numero di insiemi è uguale a $(m)$ )
e per $3$il numero più piccolo sarebbe simile
solo ogni "set" conterrebbe tutti i numeri tranne due - e ogni combinazione di questo, quindi il numero di set sarebbe qualcosa di simile $(m)$X$(m-1)/2$.
e per $4$il numero più piccolo sarebbe simile
solo ogni "set" conterrebbe tutti i numeri tranne tre - e ogni combinazione di questo, quindi il numero di set sarebbe qualcosa di simile $(m)$X$(m-1)$X$(m-2)/(3!)$.
Diviso per 3! perché prendo solo una combinazione di alcuni$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$).
e così via
Questa soluzione è stata originariamente ispirata alla soluzione di athin , ma con un modo migliorato di generare la somma dei due numeri più piccoli. Ora, è una variante della soluzione di Bass poiché, come suggerito da loro nei commenti, possiamo cambiare la somma in un massimo, e quindi non abbiamo bisogno di sottrarre il numero più piccolo alla fine.
Indicizziamo gli input come $x_0, x_1, \dots, x_{m-1}$. Scrivi i numeri$0, 1, \dots, m-1$in binario. Per ciascuno$k=1,2,\dots,\lceil\log_2 m\rceil$, permettere $A_k$ essere il minimo di tutti $x_i$ tale che $i$ ha un $0$ nel $k$-th posizione; permettere$B_k$ essere il minimo di tutti $x_i$ tale che $i$ ha un $1$ nel $k$-th posizione. Allora la nostra soluzione è$$\min(\max(A_1,B_1),\max(A_2,B_2),\dots,\max(A_k,B_k)).$$ Il numero di $x$è in questa espressione $m \lceil \log_2 m \rceil$.
Ecco perché funziona:
Ogni $\max(A_k,B_k)$sarà il massimo di due elementi, quindi è almeno il secondo elemento più piccolo. D'altra parte, se$x_i$ e $x_j$ sono i due più piccoli $x$Allora deve esserci una posizione $k$ dove le rappresentazioni binarie di $i$ e $j$differire; dire,$i$ ha un $0$ nel $k$-esima posizione, e $j$ ha un $1$. Allora avremo$A_k = x_i$ e $B_k = x_j$, così $\max(A_k,B_k) = \max(x_i,x_j)$apparirà sicuramente nel minuto che prendiamo. Nessun altro$\max(A_{k'}, B_{k'})$ può essere più piccolo, quindi $\max(x_i,x_j)$, il secondo elemento più piccolo, è la nostra risposta finale.
Ecco un esempio della formula finita per $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).$$
Ed ecco un diagramma di quella soluzione disegnata da humn :
Possiamo in qualche modo generalizzare questo a un file $O(m \log m)$ soluzione per trovare il file $k^{\text{th}}$elemento più piccolo, basandosi su una risposta Math.SE scritta un anno fa da un individuo intelligente e bello.
Dico "una specie di" perché questa è solo una costruzione casuale. Non nel senso che funzioni solo su alcuni input casuali. È casuale nel senso che descriverò un metodo per generare una formula con una certa casualità nel metodo; con probabilità positiva, ci darà una formula che funziona sempre per tutti gli input.
Ecco come.
Una "clausola" nella nostra formula è simile alla seguente. Ci siamo lasciati$\{1,2,\dots,m\}$ in $k$ imposta $S_1, S_2, \dots, S_k$e poi prendi $$\max\{\min\{x_i : i \in S_1\}, \min\{x_i : i \in S_2\}, \dots, \min\{x_i : i \in S_k\}\}.$$ Il valore che questo genera è sempre un massimo di $k$elementi distinti, quindi è almeno il file$k^{\text{th}}$il più piccolo. E se il file$k$ elementi più piccoli capita di essere distribuiti in modo uniforme tra $S_1, \dots, S_k$, Allora il valore della clausola è il$k^{\text{th}}$ elemento più piccolo.
Per assicurarci che ciò accada sempre, generiamo molte clausole a caso: per ciascuna $i \in \{1,2,\dots,m\}$, scegliamo (indipendentemente e in modo uniforme a caso) di metterlo in uno dei $S_1, \dots, S_k$. Come mostrato nella risposta Math.SE a cui ho collegato, se generiamo$\frac{k^k}{k!} \ln \binom mk \approx k e^k \ln m$clausole, quindi con probabilità positiva sarà vero per qualsiasi $k$variabili, c'è una clausola che le separa. Quando ciò accadrà, la nostra formula finale sarà il minimo di tutte queste clausole.
Ecco ancora un altro approccio. Si trova tra i metodi di @ athin e @Jan Ivan .
Si basa sull'osservazione che il secondo numero più piccolo è
il numero più piccolo che è maggiore (o uguale a) un altro numero.
Ciò significa che possiamo farlo
un min () su tutti i possibili max () a coppie: $$\min\left(\max(x_1, x_2), \max(x_1,x_3),\ldots, \max(x_{m-1}, x_m)\right)$$
Per ricontrollare che funzioni, dobbiamo solo notarlo
il più piccolo numero non potrà mai presentarsi come uno dei max () es, a meno che non ci sia un pareggio per il più piccolo, che è esattamente il caso particolare quando farlo vogliamo che vedere.