Encomende 40 varas

15

Temos 40 varas da mesma largura, mas com alturas diferentes. Quantos arranjos são possíveis para colocá-los um ao lado do outro, de modo que, quando olhamos da direita, vemos 10 paus e quando olhamos da esquerda, vemos novamente exatamente 10 paus?

Por exemplo, esse pedido é:Um exemplo de pedido

Paus pretos estão escondidos, paus vermelhos são os que você pode ver quando olha da esquerda, os paus azuis são os que você vê quando olha da direita e da roxa (ou seja, a mais longa) é a que pode ser vista. de ambos os lados.

Como casos de teste:

  • Se tivéssemos 3 varas, o número de pedidos para ver 2 da esquerda e 2 da direita é 2
  • Se tivéssemos 5 varas, o número de pedidos para ver 3 da esquerda e 3 da direita é 6
  • Se tivéssemos 10 varas, o número de pedidos para ver 4 da esquerda e 4 da direita é 90720
code-golf combinatorics permutations camarada
fonte
13
Você pode evitar perguntas com uma saída fixa, porque a resposta ideal para código-golfe provavelmente imprimirá apenas o resultado sem calculá-lo. Eu recomendo fazer a pergunta tem algumas entradas variáveis, por exemplo, N varas de tal forma que você vê K deles da esquerda / direita, onde N e K são inteiros de entrada
SP3000
4
Se você alterar as especificações para que os programas recebam informações (não vejo por que não - você já possui os casos de teste), convém pensar se deseja ou não colocar um limite de tempo nos programas.
Sp3000
1
"É necessário usar o programa publicado para calcular o caso 40/10" deve ser um limite de tempo suficientemente bom.
Feersum
1
Não consigo superar o fato de que 10!/40 = 90720... isso é coincidência?
Tim
1
@ Tim Qual é o significado de 90720? CEP para Los Alamitos, CA ?
Digital Trauma

Respostas:

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

O número de paus visíveis também é chamado de Números de arranha-céu , depois do jogo de lápis / grade. Este código é baseado (apenas ligeiramente alterado) na fórmula do OEIS A218531 . Não conheço muito PARI, mas acho que não há muito para jogar aqui.

Os casos de teste são todos mostrados em ideone.com . O resultado para f(40,10)é:

192999500979320621703647808413866514749680
Geobits
fonte
1
Há uma boa razão para a fórmula. O número de permutações com vmanípulos visíveis à esquerda é o número de Stirling s(n,v). Se o manípulo mais alto estiver na posição k, os manípulos visíveis à esquerda são o manípulo e os manípulos visíveis à esquerda na sub permutação à esquerda dos k-1valores à esquerda da posição k. Portanto, para ter vpaus visíveis à esquerda e paus visíveis à vdireita , temos s(k,v-1)opções para permutar a metade esquerda, s(n-k-1,v-1)permutar a metade direita e binomial(n-1,k)opções para dividir os paus nas duas metades.
Xnor 12/05
@xnor Eles dão basicamente essa explicação no PDF vinculado, mas o seu está redigido em IMO muito melhor.
Geobits
Você pode economizar 11 bytes: f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1))). Isso salva sterlingem uma variável para reutilização, deixa de fora seu último argumento, já que 1 é o padrão e subtrai 1 de n uma vez em vez de três vezes.
Charles
1

Python 3, 259 bytes

Não estou muito feliz com isso.

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)

Exemplo de entrada e saída:

10 4
90720

Ele gera todas as combinações possíveis do intervalo fornecido e os percorre, verificando cada número neles para ver se é igual ao máximo dos números anteriores. Em seguida, ele faz o mesmo ao contrário, e se a contagem para a frente (t) = a contagem para trás (d) = o número de exibição fornecido (k), é válido. Adiciona isso a um contador (c) e imprime isso no final.

Tim
fonte
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-golfe um pouco:

    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)))
    }
modelo
fonte
0

Pitão - 38 36 bytes

Basicamente, uma porta da resposta R. Muito lento, nem pode ser concluído 10, 4online.

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

As únicas coisas que Pyth não possui são cummax e os ==vetores over, mas esses precisaram de apenas alguns bytes para serem implementados.

Explicação e mais golfe em breve.

Experimente aqui online .

Maltysen
fonte