Bestellen Sie 40 Sticks

15

Wir haben 40 Stöcke gleicher Breite, aber unterschiedlicher Höhe. Wie viele Anordnungen gibt es, um sie nebeneinander zu stellen, sodass wir von rechts gesehen 10 Stöcke sehen und von links gesehen genau 10 Stöcke?

Zum Beispiel ist eine solche Bestellung:Ein Bestellbeispiel

Schwarze Stöcke sind versteckt, rote Stöcke sind diejenigen, die Sie sehen können, wenn Sie von links schauen, die blauen Stöcke sind diejenigen, die Sie sehen können, wenn Sie von rechts schauen, und lila (dh der längste) ist derjenige, der gesehen werden kann von beiden Seiten.

Als Testfälle:

  • Wenn wir 3 Stöcke hatten, ist die Anzahl der Bestellungen 2 von links und 2 von rechts ist 2
  • Wenn wir 5 Sticks hatten, sehen wir 3 von links und 3 von rechts ist 6
  • Wenn wir 10 Sticks hatten, ist die Anzahl der Bestellungen, um 4 von links und 4 von rechts zu sehen, 90720
code-golf combinatorics permutations Kumpel
quelle
13
Möglicherweise möchten Sie Fragen mit einer festen Ausgabe vermeiden, da die optimale Code-Golf-Antwort wahrscheinlich nur das Ergebnis ausgibt, ohne es zu berechnen. Ich würde empfehlen , die Frage ein paar variable Eingänge haben, damit beispielsweise N - Sticks , so dass Sie von K von ihnen links sehen / rechts, wobei N und K eingegeben ganzen Zahlen
SP3000
4
Wenn Sie die Spezifikation so ändern, dass Programme Eingaben übernehmen (ich verstehe nicht, warum nicht - Sie haben bereits die Testfälle), möchten Sie möglicherweise darüber nachdenken, ob Sie ein Zeitlimit für Programme festlegen möchten oder nicht.
Sp3000,
1
"Muss Ihr veröffentlichtes Programm verwenden, um den Fall 40/10 zu berechnen" sollte eine ausreichend gute Frist sein.
Feersum
1
Ich kann nicht darüber hinwegkommen, dass 10!/40 = 90720... das Zufall ist?
Tim,
1
@ Tim Was ist die Bedeutung von 90720? Postleitzahl für Los Alamitos, CA ?
Digitales Trauma

Antworten:

8

PARI / GP, 80

f(n,v)=abs(sum(k=1,n-1,binomial(n-1,k)*stirling(k,v-1,1)*stirling(n-k-1,v-1,1)))

Die Anzahl der sichtbaren Sticks wird nach dem Bleistift- / Rasterspiel auch als Skyscraper Numbers bezeichnet . Dieser Code basiert auf (nur geringfügig geänderten) Formeln aus OEIS A218531 . Ich weiß nicht viel über PARI, aber ich glaube wirklich nicht, dass es hier draußen viel zu golfen gibt.

Testfälle werden alle auf ideone.com gezeigt . Das Ergebnis für f(40,10)ist:

192999500979320621703647808413866514749680
Geobits
quelle
1
Es gibt einen guten Grund für die Formel. Die Anzahl der Permutationen mit vlinks sichtbaren Sticks ist die Stirlingzahl s(n,v). Wenn sich der höchste Stick an der Position befindet k, sind die links sichtbaren Sticks der Stick und die links sichtbaren Sticks in der Sub-Permutation links von den k-1Werten links von der Position k. Um also vlinks und vrechts sichtbare Sticks zu haben, hat man die s(k,v-1)Wahl, die linke und s(n-k-1,v-1)die rechte Hälfte zu permutieren und die binomial(n-1,k)Wahl, die Sticks in zwei Hälften aufzuteilen.
Donnerstag,
@xnor Sie geben im Grunde diese Erklärung in der verknüpften PDF, aber Ihre ist viel besser formuliert IMO.
Geobits
Sie können 11 Bytes speichern: f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1))). Dies speichert sterlingin einer Variablen zur Wiederverwendung, lässt das letzte Argument aus, da 1 die Standardeinstellung ist, und subtrahiert 1 von n einmal anstatt dreimal.
Charles
1

Python 3, 259 Bytes

Nicht sehr glücklich damit.

import itertools as i
x=input().split()
y,k=x
y=int(y)
c=0
x=list(i.permutations(list(range(1,y+1))))
for s in x:
 t=d=0;l=s[::-1]
 for i in range(y):
  if max(s[:i+1])==s[i]:t+=1
 for i in range(y):
  if max(l[:i+1])==l[i]:d+=1
 if t==d==int(k):c+=1
print(c)

Beispiel für Ein- und Ausgabe:

10 4
90720

Es generiert alle möglichen Kombinationen des angegebenen Bereichs und durchläuft sie dann in einer Schleife, wobei jede Zahl in ihnen überprüft wird, um festzustellen, ob sie dem Maximum der vorherigen Zahlen entspricht. Es macht dann dasselbe rückwärts und wenn die Zählung vorwärts (t) = die Zählung rückwärts (d) = die gegebene Ansichtsnummer (k) ist, ist es eine gültige. Dies wird zu einem Zähler (c) hinzugefügt und am Ende ausgedruckt.

Tim
quelle
0

R 104

function(N,K)sum(sapply(combinat::permn(N),function(x)(z=function(i)sum(cummax(i)==i)==K)(x)&z(rev(x))))

Ein wenig entgolfen:

    function(N,K) {
      all_perm <- combinat::permn(N)
      can_see_K_from_left <- function(i)sum(cummax(i) == i) == K
      can_see_K_from_both <- function(x)can_see_K_from_left(x) &
                                        can_see_K_from_left(rev(x))
      return(sum(sapply(all_perm, can_see_K_from_both)))
    }
Flodel
quelle
0

Pyth - 38 36 Bytes

Grundsätzlich ein Port der R-Antwort. Ziemlich langsam, kann nicht einmal 10, 4online abschließen .

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

Die einzigen Dinge, die Pyth nicht hat, sind Cummax und das == Over-Vektoren, aber die Implementierung dauerte nur ein paar Bytes.

Erklärung und weiteres Golfen folgen in Kürze.

Probieren Sie es hier online .

Maltysen
quelle