Ordene 40 palos

15

Tenemos 40 palos del mismo ancho pero diferentes alturas. ¿Cuántos arreglos hay posibles para ponerlos uno al lado del otro para que cuando miremos desde la derecha veamos 10 palos y cuando miremos desde la izquierda volvamos a ver exactamente 10 palos?

Por ejemplo, tal orden es:Un ejemplo de pedido

Los palos negros están ocultos, los palos rojos son los que puedes ver cuando miras desde la izquierda, los palos azules son los que puedes ver cuando miras desde la derecha y el morado (es decir, el más largo) es el que se puede ver visto de ambos lados.

Como casos de prueba:

  • Si tuviéramos 3 palos, el número de pedidos para ver 2 desde la izquierda y 2 desde la derecha es 2
  • Si tuviéramos 5 palos, el número de pedidos para ver 3 desde la izquierda y 3 desde la derecha es 6
  • Si tuviéramos 10 palos, el número de pedidos para ver 4 desde la izquierda y 4 desde la derecha es 90720
code-golf combinatorics permutations compañero
fuente
13
Es posible que desee evitar preguntas con una salida fija porque la respuesta óptima de código de golf probablemente solo imprima el resultado sin calcularlo. Recomiendo que la pregunta tenga algunas entradas variables, por ejemplo, N palos de modo que vea K de ellos de izquierda a derecha, donde N y K son enteros de entrada
Sp3000
44
Si cambia la especificación para que los programas tomen información (no veo por qué no, ya tiene los casos de prueba), es posible que desee pensar si desea o no poner un límite de tiempo a los programas.
Sp3000
1
"Debe usar su programa publicado para calcular el caso 40/10" debería ser un límite de tiempo suficientemente bueno.
fiesta
1
No puedo superar el hecho de que 10!/40 = 90720... ¿es una coincidencia?
Tim
1
@Tim ¿Cuál es el significado de 90720? Código postal para Los Alamitos, CA ?
Trauma digital

Respuestas:

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

El número de palos visibles también se llama Skyscraper Numbers , después del juego de lápiz / cuadrícula. Este código se basa en (solo ligeramente alterado) la fórmula de OEIS A218531 . No sé mucho PARI, pero realmente no creo que haya mucho para jugar golf aquí.

Los casos de prueba se muestran en ideone.com . El resultado para f(40,10)es:

192999500979320621703647808413866514749680
Geobits
fuente
1
Hay una buena razón para la fórmula. El número de permutaciones con vpalos visibles a la izquierda es el número de Stirling s(n,v). Si el palo más alto está en posición k, los palos visibles a la izquierda son ese palo y los palos visibles a la izquierda en la subpermutación a la izquierda de los k-1valores a la izquierda de la posición k. Entonces, para tener vpalos visibles a la izquierda y palos visibles a la vderecha, uno tiene s(k,v-1)opciones para permutar la mitad izquierda, s(n-k-1,v-1)para permutar la mitad derecha y binomial(n-1,k)opciones para dividir los palos en las dos mitades.
xnor
@xnor Dan básicamente esa explicación en el PDF vinculado, pero la tuya está redactada mucho mejor en mi opinión.
Geobits
Puede guardar 11 bytes: f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1))). Esto guarda sterlingen una variable para su reutilización, deja de lado su último argumento, ya que 1 es el valor predeterminado y resta 1 de n una vez en lugar de tres veces.
Charles
1

Python 3, 259 bytes

No muy contento con esto.

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)

Ejemplo de entrada y salida:

10 4
90720

Genera todas las combinaciones posibles del rango proporcionado, y luego las recorre, verificando cada número en ellas para ver si es igual al máximo de los números anteriores. Luego hace lo mismo al revés, y si el conteo hacia adelante (t) = el conteo hacia atrás (d) = el número de vista dado (k) es válido. Agrega esto a un contador (c) e imprime eso al final.

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

Des golf un poco:

    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
fuente
0

Pyth - 38 36 bytes

Básicamente un puerto de la respuesta R. Bastante lento, ni siquiera se puede completar en 10, 4línea.

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

Las únicas cosas que Pyth no tiene son cummax y los ==vectores over, pero esos solo tomaron unos pocos bytes para implementar.

Explicación y más golf próximamente.

Pruébalo aquí en línea .

Maltysen
fuente