Commandez 40 bâtons

15

Nous avons 40 bâtons de mêmes largeurs mais de hauteurs différentes. Combien d'arrangements est-il possible de les mettre les uns à côté des autres pour que lorsque nous regardons de droite nous voyons 10 bâtons et quand nous regardons de gauche nous voyons à nouveau exactement 10 bâtons?

Par exemple, une telle commande est:Un exemple de commande

Les bâtons noirs sont cachés, les bâtons rouges sont ceux que vous pouvez voir lorsque vous regardez de gauche, les bâtons bleus sont ceux que vous pouvez voir lorsque vous regardez de droite et le violet (c'est-à-dire le plus long) est celui que vous pouvez voir vu des deux côtés.

Comme cas de test:

  • Si nous avions 3 bâtons, le nombre de commandes pour voir 2 de gauche et 2 de droite est 2
  • Si nous avions 5 bâtons, le nombre de commandes pour voir 3 de gauche et 3 de droite est 6
  • Si nous avions 10 bâtons, le nombre de commandes pour voir 4 de gauche et 4 de droite est 90720
code-golf combinatorics permutations Copain
la source
13
Vous voudrez peut-être éviter les questions avec une sortie fixe, car la réponse optimale code-golf imprimera probablement le résultat sans le calculer. Je recommanderais que la question ait quelques entrées variables, par exemple N sticks de sorte que vous en voyiez K de gauche / droite, où N et K sont des entiers d'entrée
Sp3000
4
Si vous modifiez la spécification pour que les programmes prennent en entrée (je ne vois pas pourquoi - vous avez déjà les cas de test), vous voudrez peut-être vous demander si vous voulez ou non limiter les programmes.
Sp3000
1
"Doit utiliser votre programme affiché pour calculer le cas 40/10" devrait être un délai suffisant.
feersum
1
Je ne peux pas surmonter le fait que 10!/40 = 90720... est-ce une coïncidence?
Tim
1
@Tim Quelle est la signification du 90720? Code postal de Los Alamitos, CA ?
Digital Trauma,

Réponses:

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)))

Le nombre de bâtons visibles est également appelé numéros de gratte-ciel , après le jeu crayon / grille. Ce code est basé sur (seulement légèrement modifié) la formule de OEIS A218531 . Je ne connais pas beaucoup PARI, mais je ne pense vraiment pas qu'il y ait beaucoup à jouer au golf ici.

Les cas de test sont tous présentés sur ideone.com . Le résultat pour f(40,10)est:

192999500979320621703647808413866514749680
Géobits
la source
1
Il y a une bonne raison pour la formule. Le nombre de permutations avec vdes bâtons visibles à gauche est le nombre de Stirling s(n,v). Si le bâton le plus haut est en position k, alors les bâtons visibles à gauche sont ce bâton et les bâtons visibles à gauche dans la sous-permutation à gauche des k-1valeurs à gauche de la position k. Donc, pour avoir vdes bâtons visibles à gauche et des bâtons visibles à vdroite, on a le s(k,v-1)choix de permuter la moitié gauche, s(n-k-1,v-1)de permuter la moitié droite et binomial(n-1,k)de diviser les bâtons en deux moitiés.
xnor
@xnor Ils donnent essentiellement cette explication dans le PDF lié, mais le vôtre est formulé beaucoup mieux IMO.
Geobits
Vous pouvez enregistrer 11 octets: f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1))). Cela enregistre sterlingdans une variable pour la réutilisation, laisse son dernier argument, car 1 est la valeur par défaut, et soustrait 1 de n une fois plutôt que trois fois.
Charles
1

Python 3, 259 octets

Pas très content de ça.

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)

Exemple d'entrée et de sortie:

10 4
90720

Il génère toutes les combinaisons possibles de la plage fournie, puis les parcourt en boucle, vérifiant chaque nombre en eux pour voir s'il est égal au maximum des nombres précédents. Il fait ensuite la même chose en arrière, et si le compte en avant (t) = le compte en arrière (d) = le numéro de vue donné (k), il est valide. Il ajoute cela à un compteur (c) et l'imprime à la fin.

Tim
la source
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))))

De-golf un peu:

    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
la source
0

Pyth - 38 36 octets

Fondamentalement, un port de la réponse R. Assez lent, je ne peux même pas terminer en 10, 4ligne.

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

Les seules choses que Pyth n'a pas sont cummax et les ==vecteurs over, mais ceux-ci n'ont mis que quelques octets à implémenter.

Explication et golf à venir bientôt.

Essayez-le ici en ligne .

Maltysen
la source