Jak podejść do wyzwania Vertical Sticks

23

Dane są wartości całkowitych $Y=\{y_1,...,y_n\}$ który reprezentuje $n$ segmentów linii, tak że punktami końcowymi segmentu $i$ są $(i, 0)$ i $(i, y_i)$ . Wyobraź sobie, że od góry każdego segmentu promień poziomy jest wystrzeliwany w lewo, a promień ten zatrzymuje się, gdy dotyka innego segmentu lub uderza w oś y. Skonstruować tablicę liczb całkowitych n, $v_1, ..., v_n$ , gdzie $v_i$ jest równe długości promienia wystrzelonego z góry segmentu $i$ . Zdefiniować $V(y_1, ..., y_n) = v_1 + ... + v_n$ .

Na przykład, jeśli mamy $Y=[3,2,5,3,3,4,1,2]$ , a następnie $[v_1, ..., v_8] = [1,1,3,1,1,3,1,2]$ , jak pokazano na poniższym obrazku:

wprowadź opis zdjęcia tutaj

Dla każdego permutacji o , można obliczyć . Jeśli zdecydujemy się równomiernie losowej permutacji z , jaka jest oczekiwana wartość $p$ $[1,...,n]$ $V(y_{p_1}, ..., y_{p_n})$ $p$ $[1,...,n]$ ? $V(y_{p_1}, ..., y_{p_n})$

Jeśli rozwiążemy ten problem, stosując podejście naiwne, nie będzie ono wydajne i będzie działać praktycznie wiecznie dla . Wierzę, że możemy podejść do tego problemu, obliczając niezależnie wartość oczekiwaną dla każdego drążka, ale wciąż muszę wiedzieć, czy istnieje inne skuteczne podejście do tego problemu. Na jakiej podstawie możemy obliczyć oczekiwaną wartość dla każdego drążka niezależnie? $n=50$ $v_i$

algorithms probability-theory

— Raphael
źródło

Możesz użyć liniowości oczekiwań. To pytanie jest prawdopodobnie bardziej odpowiednie na mat.SE

23

Wyobraź sobie inny problem: gdybyś musiał umieścić drążków o jednakowej wysokości w szczelinach, to oczekiwana odległość między drążkami (i oczekiwana odległość między pierwszym drążkiem a hipotetyczną szczeliną oraz oczekiwana odległość między ostatnim drążkiem a hipotetyczną gniazdo ) to $k$ $n$ $0$ $n+1$ ponieważ istniejeszczelin pasujących do długości. $\frac{n+1}{k+1}$ $k+1$ $n+1$

Wracając do tego problemu, konkretny drążek jest zainteresowany liczbą drążków (w tym siebie), które są tak wysokie lub wyższe. Jeśli liczba ta wynosi , to oczekiwana przerwa po jej lewej stronie również wynosi $k$ . $\frac{n+1}{k+1}$

Algorytm polega więc na znalezieniu tej wartości dla każdego drążka i zsumowaniu oczekiwań. Na przykład, zaczynając od wysokości , liczba drążków o większej lub równej wysokości wynosi więc oczekiwane jest $[3,2,5,3,3,4,1,2]$ $[5,7,1,5,5,2,8,7]$ . $\frac96+\frac98+\frac92+\frac96+\frac96+\frac93+\frac99+\frac98 = 15.25$

Jest to łatwe do zaprogramowania: na przykład pojedyncza linia w R.

V <- function(Y){ (length(Y) + 1) * sum( 1 / (rowSums(outer(Y, Y, "<=")) + 1) ) }

podaje wartości w danych wyjściowych próbki w pierwotnym problemie

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15

— Henz
źródło

1

Bardzo interesujące. Czy możesz nieco wyjaśnić, dlaczego oczekiwana odległość między drążkami wynosi

; ponieważ nie jest jasne (przynajmniej dla mnie), w jaki sposób zostało obliczone. Dziękuję Ci.

(n + 1) / (k + 1)

$(n+1)/(k+1)$

— M. Alaggan

W moim pierwszym przypadku

drążków o jednakowej wysokości istnieje długość

należy wypełnić

szczelinami, więc średnia przerwa wynika z dzielenia się jedna przez drugą. Jest to oczekiwana przerwa (lub promień poziomy) przed każdym konkretnym drążkiem (i od ostatniego drążka do

). Przenosi się do pierwotnego pytania, biorąc pod uwagę drążki, które są tak wysokie lub wyższe niż jakikolwiek konkretny drążek.

k

$k$

n + 1

$n+1$

k + 1

$k+1$

n + 1

$n+1$

— Henry

Bardzo dobrze. To całkowicie podważa moje rozwiązanie; jeżeli wszystkie wysokości są różne, wówczas

.

E [V] = \sum_{k = 1}^{n} \frac{n + 1}{k + 1} = (n + 1) (H_{n + 1} - 1) = (n + 1) H_{n} - n

$E[V] = \sum_{k=1}^n \frac{n+1}{k+1} = (n+1)(H_{n+1} - 1) = (n+1)H_n - n$

— JeffE

2

@Henry: Dla k-ki o równej wysokości, problem n-slotów, jakie było twoje uzasadnienie dla średniej długości = (n + 1) / (k + 1)? Jeśli mam k-ki i chcę poznać średnią długość promienia jednego z tych kijów w każdej permutacji tych k-ki w n szczelinach, to w rzeczywistości jest równy twojemu wynikowi, ale nie rozumiem dlaczego. Czy jest jakaś logika, czy też wywnioskowałeś ją matematycznie z robienia tego, co opisałem dla 1 kija i n szczelin, a następnie 2 kijów i n, szczelin, ... kijków, n szczelin i zauważenia, że jest on równy (n + 1) / ( k + 1)? Wspominasz o dodaniu gniazda n + 1. To wydaje się bardzo sprzeczne z intuicją.

— Alexandre

3

To pytanie, z którym już sobie poradziłem. Zacznij od okrągłego stołu z

miejscami,

osób i posadź ich losowo. Odległości między osobami są oczywiście równe średniej

. Teraz przełamać stolik w

osoby, usunąć tę osobę i swoją siedzibę i wyprostuj tabeli. Teraz masz pytanie o

miejsc i

osób, ale tę samą własność iid i ten sam środek. (Znajdź rzadki rym przez miesiąc )

n + 1

$n+1$

k + 1

$k+1$

(n + 1) / (k + 1)

$(n+1)/(k+1)$

n + 1^{th}

$n+1^{\text{th}}$

n

$n$

k

$k$

— Henry

11

Rozwiązanie Henry'ego jest zarówno prostsze, jak i bardziej ogólne niż to!

to w przybliżeniu połowa oczekiwanej liczby porównań przeprowadzonych przez losowy Quicksort. $E[V]$

Zakładając, że drążki mają różne wysokości , możemy uzyskać rozwiązanie dla w formie zamkniętej w następujący sposób. $E[Y]$

Do ewentualnych wskaźników , niech jeśli i przeciwnym razie. (Jeśli elementy nie są różne, to oznacza, że jest ściśle większy niż każdy element $i\le j$ $X_{ij} = 1$ $Y_j = \max\{Y_i,...,Y_j\}$ $X_{ij}=0$ $Y$ $X_{ij}=1$ $Y_j$ .) $\{Y_i, \dots, Y_{j-1}\}$

Następnie dla dowolnego indeksu mamy (Czy widzisz dlaczego?), A zatem $j$ $v_j = \sum_{i=1}^j X_{ij}$

V. = \sum_{jot = 1}^{n} v_{jot} = \sum_{jot = 1}^{n} \sum_{ja = 1}^{jot} X_{ja jot} .

$V = \sum_{j=1}^n v_j = \sum_{j=1}^n \sum_{i=1}^j X_{ij}.$

Liniowość oczekiwań natychmiast implikuje, że

mi [V.] = mi [\sum_{1 \leq ja \leq jot \leq n} X_{ja jot}] = \sum_{1 \leq ja \leq jot \leq n} mi [X_{ja jot}] .

$E[V] = E\bigg[\sum_{1\le i\le j\le n} X_{ij}\bigg] = \sum_{1\le i\le j\le n} E[X_{ij}].$

Ponieważ wynosi lub , mamy . $X_{ij}$ $0$ $1$ $E[X_{ij}] = \Pr[X_{ij}=1]$

W końcu, i to jest ważne, ponieważ bit wartości w są różne i permutowane równomiernie każdy element podzbioru jest również może być największy element tego podzespołu. Zatem $Y$ $\{Y_i,...,Y_j\}$ . (Jeśli elementynie są odrębne, nadal mamy $\Pr[X_{ij}=1] = \frac{1}{j-i+1}$ $Y$ ). $\Pr[X_{ij}=1] \le \frac{1}{j-i+1}$

A teraz mamy trochę matematyki. gdzieoznaczatąliczbę harmonicznych.

\begin{aligned} mi [V.] & = \sum_{jot = 1}^{n} \sum_{ja = 1}^{jot} mi [X_{ja jot}] & [liniowość] \\ = \sum_{jot = 1}^{n} \sum_{ja = 1}^{jot} \frac{1}{jot - ja + 1} & [jednolitość] \\ = \sum_{jot = 1}^{n} \sum_{h = 1}^{jot} \frac{1}{h} & [h = jot - ja + 1] \\ = \sum_{h = 1}^{n} \sum_{jot = h}^{n} \frac{1}{h} & [1 \leq h \leq jot \leq n] \\ = \sum_{h = 1}^{n} \frac{n - h + 1}{h} \\ = ((n + 1) \sum_{h = 1}^{n} \frac{1}{h}) - (\sum_{h = 1}^{n} 1) \\ = (n + 1) {H.}_{n} - n \end{aligned}

$\begin{aligned} E[V] &= \sum_{j=1}^n \sum_{i=1}^j E[X_{ij}] & [\text{linearity}]\\ &= \sum_{j=1}^n \sum_{i=1}^j \frac{1}{j-i+1} & [\text{uniformity}]\\ &= \sum_{j=1}^n \sum_{h=1}^j \frac{1}{h} & [h = j-i+1]\\ &= \sum_{h=1}^n \sum_{j=h}^n \frac{1}{h} & [1\le h\le j\le n]\\ &= \sum_{h=1}^n \frac{n-h+1}{h}\\ &= \left((n+1)\sum_{h=1}^n \frac{1}{h}\right) - \left(\sum_{h=1}^n 1\right)\\ &= (n+1)H_n - n \end{aligned}$

H_{n}

$H_n$

n

$n$

Teraz obliczenie (do precyzji zmiennoprzecinkowej) w czasie powinno być banalne . $E[V]$ $O(n)$

— JeffE
źródło

Czy to zakłada, że patyki mają różną wysokość?

— Aryabhata

Tak, przyjmuje wyraźne wysokości. (Najwyraźniej źle odczytałem pytanie). Równoważność z randomizowanym szybkim sortowaniem nadal obowiązuje, gdy istnieją powiązania, ale nie rozwiązanie w formie zamkniętej.

— JeffE

4

Jak wspomniano w komentarzach, możesz użyć liniowości oczekiwania.

$y$ $y_1 \le y_2 \le \dots \le y_n$

$y_i$ $v_i = E[v_i]$

$E[\sum_{i=1}^{n} v_i] = \sum_{i=1}^{n} E[v_i]$

$E[v_i]$ $y_i$ $j$

$j-1$ $\ge y_i$

$j-1$ $\lt y_i$ $j-2$ $\ge y_i$

$E[v_i]$

Prawdopodobnie możesz to przyspieszyć, wykonując matematykę i zdobywając formułę (chociaż sam tego nie próbowałem).

Mam nadzieję, że to pomaga.

— Aryabhata
źródło

3

Rozwijając odpowiedź @Aryabhata:

$i$ $y_i$ $j$ $y_i$ $Z^{(i)}$ $z_k^{(i)}$ $y_k\geq y_i$ $z_k^{(i)}$

$Z^{(i)}$ $Y$ $Z^{(i)}$ $\dots$ $z_i^{(i)}$ $j$ $\dots$

$v_i$ $z_i^{(i)}$ $\mathbb{E}\left(v_i\right)$ $j-1$ $Z^{(i)} \setminus \\{z_i^{(i)} \\}$ $j$ $\{1,\dots,n \}$

Po obliczeniu (zgodnie z tymi liniami ) możemy postępować zgodnie z odpowiedzią @ Aryabhata.

— M. Alaggan
źródło

-2

Naprawdę nie rozumiem, czego żądasz, na podstawie tagów wydaje się, że szukasz algorytmu.

jeśli tak, jaka jest przewidywana złożoność czasu? mówiąc: „Jeśli rozwiążemy ten problem, stosując podejście naiwne, nie będzie ono wydajne i będzie działać praktycznie wiecznie dla n = 50”. wydaje mi się, że twoje naiwne podejście rozwiązuje je w wykładniczym czasie.

Mam na myśli algorytm O (n ^ 2).

assume int y[n], v[n] where v[i] initialized with 1; as described in the question
for (i=1;i<n;i++) 
   for ( j=i-1 ; j>=0 && y[j]<y[i] ; j--) v[i]++;