Partições de número inteiro restrito

8

P k (n) significa a quantidade de partições nexatamente em kpartes. Dado ne k, calcule P k (n).

Dica: P k (n) = P k (n-k) + P k-1 (n-1), com valores iniciais p 0 (0) = 1 ep k (n) = 0 se n ≤ 0 ou k ≤ 0. [Wiki]

Exemplos

n    k    Ans
1    1    1
2    2    1
4    2    2
6    2    3
10   3    8

Regras

Matthew Roh
fonte
1
Você deve indicar claramente que isso é código-golfe , mesmo que esteja marcado.
Mr. Xcoder
2
Alguém pode link para a OEIS para isso (eu supor que há um com o número de seqüências de partição Fomos correndo para o pós CnR OEIS)
Stephen
3
Eu acho que o último caso de teste deve ser 8
H.PWiz
2
Concordo com H.PWiz que o último caso de teste deve ser em 8vez de 7.
Erik the Outgolfer
2
A008284
milhas

Respostas:

3

Rápido , 76 73 bytes

func P(_ n:Int,_ k:Int)->Int{return n*k>0 ?P(n-k,k)+P(n-1,k-1):n==k ?1:0}

Experimente online!


Explicação

Como o código funciona estruturalmente?

Antes de tudo, definimos nossa função P , com dois parâmetros inteiros ne k, e dar-lhe um tipo de retorno Int, com este pedaço de código: func P(_ n:Int,_ k:Int)->Int{...}. O truque legal aqui é que dizemos ao compilador para ignorar os nomes dos parâmetros, _seguido por um espaço, o que nos salva dois bytes quando chamamos a função. returné obviamente usado para retornar o resultado do nosso ternário aninhado descrito abaixo.

Outro truque que usei foi o de n*k>0poupar alguns bytes n>0&&k>0. Se a condição for verdadeira (ambos os números inteiros ainda são maiores que 0), então recursivamente chamamos nossa função com ndecrementada de kcomo nova ne kpermanece a mesma, e adicionamos o resultado deP() com ne kdecrementada por 1. Se a condição não for verdadeira , retornamos um 1ou 0dependendo se né igual a k.

Como o algoritmo recursivo funciona?

Sabemos que o primeiro elemento da sequência é p 0 (0) e, portanto, verificamos se os dois números inteiros são positivos ( n*k>0). Se não forem maiores que 0, verificamos se são iguais ( n==l ?1:0), sendo dois casos:

  • Existe exatamente 1 partição possível e, portanto, retornamos 1, se os números inteiros forem iguais.

  • Não há partições se uma delas já for 0 e a outra não.

No entanto, se ambos forem positivos, chamamos recursivamente Pduas vezes, adicionando os resultados de P(n-k,k)e P(n-1,k-1). E rodamos novamente atén atingir 0.


* Nota: Os espaços não podem ser removidos.

Mr. Xcoder
fonte
2

Python 2 , 61 55 51 50 bytes

-10 bytes graças a Erik, o Outgolfer. -1 byte graças ao Sr. Xcoder.

Eu direi que copiei a dica do OP e a traduzi para Python. : P

P=lambda n,k:n*k>0and P(n-k,k)+P(n-1,k-1)or+(n==k)

Experimente online!

totalmente humano
fonte
1
Isso quebra no último caso de teste de 10, 3. Demasiada recursão
jkelm
1
(n>0and k>0)->n>0<k
Erik the Outgolfer
1
Além disso, você pode fazer em +(n==k)vez de [0,1][n==k].
Erik the Outgolfer
1
Você não precisa do espaço or +.
Erik the Outgolfer
1
50 bytes , substitua n>0<k andporn*k>0and
Mr. Xcoder
2

Mathematica, 33 bytes

Length@IntegerPartitions[#,{#2}]&

aqui está a tabela nxk

 \k->
 n1  0  0   0   0   0   0   0   0   0  
 |1  1  0   0   0   0   0   0   0   0  
 v1  1  1   0   0   0   0   0   0   0  
  1  2  1   1   0   0   0   0   0   0  
  1  2  2   1   1   0   0   0   0   0  
  1  3  3   2   1   1   0   0   0   0  
  1  3  4   3   2   1   1   0   0   0  
  1  4  5   5   3   2   1   1   0   0  
  1  4  7   6   5   3   2   1   1   0  
  1  5  8   9   7   5   3   2   1   1  
J42161217
fonte
1
Claro. Eu sabia que havia um prédio.
Matthew Roh
A Mathematica Simplificado porta iria economizar 13 bytes aqui eu acredito que ( Length-> Len`1e IntegerPartitions->Int`7
Jonathan Allan
@ JonathanAllan Na verdade, estou fazendo uma versão super curta disso. Espero que eu possa terminar até o final do mês
JungHwan Min 26/07/17
2

JavaScript (ES6), 42 40 39 bytes

Eu acho que isso funciona.

f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y

Tente

k.value=(
f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y
)(i.value=10,j.value=3)
onchange=_=>k.value=f(+i.value,+j.value)
*{font-family:sans-serif}input{margin:0 5px 0 0;width:100px;}#j,#k{width:50px;}
<label for=i>n: </label><input id=i type=number><label for=j>k: </label><input id=j type=number><label for=k>P<sub>k</sub>(n): </label><input id=k readonly>

Shaggy
fonte
2

MATL , 14 bytes

y:Z^!S!Xu!Xs=s

Experimente online!

Explicação

Considere entradas 6, 2.

y     % Implicitly take the two inputs. Duplicate from below
      % STACK: 6, 2, 6
:     % Range
      % STACK: 6, 2, [1 2 3 4 5 6]
Z^    % Cartesian power
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 1; 2 2; ...; 6 6]
!S!   % Sort each row
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 1 2; 2 2; ...; 6 6]
Xu    % Unique rows
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 2; ...; 6 6]
!Xs   % Sum of each row, as a row vector
      % STACK: 6, [2 3 ... 6 7 4 ... 12]
=     % Equals, element-wise
      % STACK: [0 0 ... 1  0 0 ... 0]
s     % Sum. Implicitly display
      % STACK: 3
Luis Mendo
fonte
Honestamente, estou surpreso que o MATL não tenha uma "partição inteira" embutida ou algo assim.
Erik the Outgolfer
@ Sanchises Deve estar funcionando agora. Obrigado por me dizer!
Luis Mendo
Sem problemas. Eu estava apenas brincando com ele para entender seu método (que geralmente é mais fácil para casos pequenos) quando encontrei o erro.
Sanchises
1

Haskell, 41 bytes

0#0=1
n#k|n*k>0=(n-k)#k+(n-1)#(k-1)
_#_=0

Experimente online!

nimi
fonte
0

Gelatina , 13 bytes

Eu tenho um sentimento sabe esta abordagem básica não vai ser o golfiest!

RŒṖL€€Ṣ€QṀ€=S

Experimente online!

Jonathan Allan
fonte
Sim, não é (veja minha resposta Jelly na parte inferior).
Erik the Outgolfer
Oh não boliche Código
Matthew Roh
@EriktheOutgolfer Se funciona, por que foi excluído?
Jonathan Allan
@Jonathan refresh
Matthew Roh
@ JonathanAllan Foi excluído antes de um caso de teste ser corrigido.
Erik the Outgolfer
0

CJam , 18 bytes

{_,:)@m*:$_&::+e=}

Experimente online!

Espera entradas ao contrário, ou seja, em k nvez de n k.

Erik, o Outgolfer
fonte
0

Scala , 73 bytes

Bem, este é um uso fácil e não resolvido da dica do OP.

ke nsão os parâmetros da minha função recursiva f. Vejo link do TIO para o contexto.

Como isso é recursivo, devo incluir a função def na contagem de bytes?

(k,n)match{case(0,0)=>1
case _ if k<1|n<1=>0
case _=>f(n-k,k)+f(n-1,k-1)}

Experimente online!

V. Courtois
fonte
0

R (+ pryr), 49 bytes

f=pryr::f(`if`(k<1|n<1,!n+k,f(n-k,k)+f(n-1,k-1)))

Que avalia a função recursiva

function (k, n) 
if (k < 1 | n < 1) !n + k else f(n - k, k) + f(n - 1, k - 1)

(k < 1 | n < 1)verifica se algum dos estados iniciais é atendido. !n + kavalia como TRUE (1) se ambos ne ksão 0 e FALSE (0) caso contrário. f(n - k, k) + f(n - 1, k - 1)lida com a recursão.

JAD
fonte