Wie man sich der vertikalen Sticks-Herausforderung nähert?

Question

dieses Problem von interviewstreet.com

gegebener Gruppe von ganzen Zahlen Y = y1, ... aufgenommen wird, yn, wir n Liniensegmente so, dass Endpunkte des Segments haben i (i, 0) und (i, yi). Stellen Sie sich vor, dass aus der Oberseite jedes Segments ein horizontaler Strahl nach links geschossen wird, und dieser Strahl stoppt, wenn er ein anderes Segment berührt oder auf die y-Achse trifft. Wir konstruieren ein Array von n ganzen Zahlen, v1, ..., vn, wobei vi ist gleich Länge des Strahls von der Spitze des Segments i erschossen. Wir definieren V (y1, ..., yn) = v1 + ... + vn. Wenn wir beispielsweise Y = [3,2,5,3,3,4,1,2] haben, dann gilt v1, ..., v8 = [1,1,3,1,1 , 3,1,2], wie unten in der Abbildung dargestellt:

von [1 für jede Permutation p, ..., n], können wir berechnen, V (YP1, ..., ypn). Wenn wir eine gleichmäßig zufällige Permutation p von [1, ..., n] wählen, was ist der erwartete Wert von V (yp1, ..., ypn)?

Eingangsformat

Erste Zeile der Eingabe enthält eine einzelne ganze Zahl T (1 < = T < = 100). T Testfälle folgen.

Die erste Zeile jedes Testfalls ist eine einzelne ganze Zahl N (1 < = N < = 50). Die nächste Zeile enthält positive ganze Zahlen y1, ..., yN getrennt durch einzelnes Leerzeichen (0 < yi < = 1000).

Ausgabeformat

Für jeden Testfall Ausgangserwartungswert von V (YP1, ..., YPN), gerundet auf zwei Stellen nach dem Komma.

Probeneingangs

6 
3 
1 2 3 
3 
3 3 3 
3 
2 2 3 
4 
10 2 4 4 
5 
10 10 10 5 10 
6 
1 2 3 4 5 6 

Beispielausgabe

4.33 
3.00 
4.00 
6.00 
5.80 
11.15 

Erläuterung

Fall 1: Wir haben V (1,2,3) = 1 + 2 +3 = 6, V (1,3,2) = 1 + 2 + 1 = 4, V (2,1,3) = 1 + 1 + 3 = 5 , V (2,3,1) = 1 + 2 + 1 = 4, V (3,1,2) = 1 + 1 + 2 = 4, V (3,2,1) = 1 + 1 + 1 = 3. Der Durchschnitt dieser Werte ist 4,33.

Fall 2: Egal was die Permutation ist, V (yp1, yp2, yp3) = 1 + 1 + 1 = 3, so ist die Antwort 3.00.

Fall 3: V (y1, y2, y3) = V (y2, y1, y3) = 5, V (y1, y3, y2) = V (y2, y3, y1) = 4, V (y3, y1, y2) = V (y3, y2, y1) = 3, und der Durchschnitt dieser Werte ist 4,00.

Eine naive Lösung des Problems wird für N = 50 für immer laufen. Ich glaube, dass das Problem gelöst werden kann, indem man einen Wert für jeden Stock unabhängig berechnet. Ich muss noch wissen, ob es einen anderen effizienten Ansatz für dieses Problem gibt. Auf welcher Grundlage müssen wir den Wert für jeden Stock selbst berechnen?

Answer 1

Wie Sie richtig bemerkt, können wir Problem unabhängig für jeden Stock lösen.

Sei F (i, len) die Anzahl der Permutationen, der Strahl von Stick i ist genau len.
Dann beantworten

ist (Summe (von i, len) F (i, len) * len)/(n!)

Alle übrig bleibt, ist F (i, len zu zählen). Sei a (i) die Anzahl der Sticks j, also y_j < = y_i. b (i) - Anzahl der Stöcke, die b_j> b_i.

Um Ray Len Länge zu bekommen, müssen wir eine Situation wie diese haben.

B, l...l, O 
    len-1 times 

Wo O - Stock #i ist. B - ist Stick mit größerer Länge oder Anfang. l - bleibt mit der Höhe, weniger als ith.

Dies gibt uns 2 Fälle:
1) B ist der Anfang, dies kann in P(a(i), len-1) * (b(i)+a(i)-(len-1))! Möglichkeiten erreicht werden.
2) B ist größere Stick, dies kann in P(a(i), len-1)*b(i)*(b(i)+a(i)-len)!*(n-len) Möglichkeiten erreicht werden.

edit: korrigiert b (i) als zweites Glied in (mul) anstelle einem (i) im Fall 2.

Answer 2

wir dieses Problem lösen können, durch Abbildung aus:

wenn der k th Stock wird in i Position gesetzt, was ist die erwartete Strahllänge dieses Stockes.

Dann kann das Problem gelöst werden, indem die gesamte erwartete Länge für alle Sticks in allen Positionen addiert wird.

Lassen expected[k][i] sein die erwartete ray-Länge von k th Stick setzen in i ten Position, lassen Sie num[k][i][length] die Anzahl der Permutationen sein, dass k th Stick setzen in i ten Position mit ray-Länge gleich zu length, dann

expected[k][i] = sum(num[k][i][length] * length)/N!

Wie berechnet man num[k][i][length]? Stellen Sie beispielsweise für length=3 die folgende Grafik ein:

... GxxxI ...

I Wo die Position ist, 3 ‚x‘ bedeutet, dass wir 3-Sticks, die strikt niedriger als I sind und G heißt, wir müssen einen Stock, der als I mindestens so hoch sind. Lassen s_i die Zahl der Stöcke, die dann die k th den Stick kleiner sind, und g_i die Zahl der Stöcke sein, die größer oder gleich den k ten Stock, dann können wir einer der g_i wählen in G Lage zu versetzen, wir können jede length von s_i wählen die x Position zu füllen, so haben wir:

num[k][i][length] = P(s_i, length) * g_i * P(n-length-1-1)

Im Falle, dass alle Positionen vor I sind alle kleiner als I, brauchen wir einen größeren Stick nicht in G, dh xxxI...., haben wir:

num[k][i][length] = P(s_i, length) * P(n-length-1)

Und hier ist ein Stück Python-Code, um dieses Problem zu lösen:

def solve(n, ys): 
    ret = 0 
    for y_i in ys: 
     s_i = len(filter(lambda x: x < y_i, ys)) 
     g_i = len(filter(lambda x: x >= y_i, ys)) - 1 

     for i in range(n): 
      for length in range(1, i+1): 
       if length == i: 
        t_ret = combination[s_i][length] * factorial[length] * factorial[ n - length - 1 ] 
       else: 
        t_ret = combination[s_i][length] * factorial[length] * g_i * factorial[ n - length - 1 - 1 ] 
       ret += t_ret * length 

    return ret * 1.0/factorial[n] + n 

Answer 3

Dies ist die gleiche Frage wie https://cs.stackexchange.com/questions/1076/how-to-approach-vertical-sticks-challenge und meine Antwort gibt (das ist ein wenig einfacher als die früher hier gegeben ist) wurde:

ein anderes Problem Stellen Sie sich vor: Wenn Sie zwischen Stöcken (und dem erwarteten Abstand zwischen dem ersten Stock und einem fiktiven Schlitz 0 und dem erwarteten Abstand zwischen dem k Stangen gleicher Höhe in n Schlitzt dann den erwarteten Abstand zu legen haben letzter Stock und ein fiktiver Schlitz n+1) ist (n+1)/(k+1) da k+1 Lücken in einer Länge n+1 passen.

Zurückkehrend zu diesem Problem ist ein bestimmter Stock interessiert, wie viele Stöcke (einschließlich sich selbst) als hoch oder höher. Wenn dies k ist, dann ist die erwartete Lücke davor auch (n+1)/(k+1).

Also ist der Algorithmus einfach diesen Wert für jeden Stick zu finden und addieren die Erwartung. Zum Beispiel, beginnend mit Höhen von 3,2,5,3,3,4,1,2, ist die Anzahl der Stöcke mit einer größeren oder gleichen Höhe 5,7,1,5,5,2,8,7, so dass die Erwartung 9/6+9/8+9/2+9/6+9/6+9/3+9/9+9/8 = 15.25 ist.

Dies ist einfach zu programmieren: zum Beispiel eine einzelne Zeile in R

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

die Werte in den für Ihre Antwort sample output in the original problem

> 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