Decomposição Combinatória
No corpo deste desafio, \$\begin{pmatrix}n\\k\end{pmatrix}\$é usado para representar o número de combinações de \$k\$elementos de \$n\$, também escrito como \$\frac{n!}{k!(n-k)!}\$ou \$n\mathrm{C}r\$.
Qualquer inteiro não negativo \$m\$, para natural arbitrário (positivo) \$r\$, pode ser escrito como uma série única de \$r\$combinações tais que$$m=\sum\limits_{i=1}^{r}\begin{pmatrix}C_i\\i\end{pmatrix}$$desde que a sequência \$C\$ambos aumentam estritamente (ou seja, \$C_{\ell-1}\lneq C_\ell\$) e consiste apenas em números inteiros não negativos. \$C\$não é necessariamente único sem essas restrições.
Exemplo
Considere \$m=19\$e \$r=4\$. Valores de \$C_4\$, \$C_3\$, \$C_2\$e \$C_1\$deve ser encontrado para a equação$$19=\sum\limits_{i=1}^4\begin{pmatrix}C_i\\i\end{pmatrix}\\$$que pode ser reescrita como$$\begin{pmatrix}C_4\\4\end{pmatrix}+\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=19$$Comece encontrando o maior valor de \$C_4\$que satisfaz a desigualdade \$\begin{pmatrix}C_4\\4\end{pmatrix}\leq 19\$. \$C_4\$é seis:$$\begin{pmatrix}6\\4\end{pmatrix}+\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=19\\15+\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=19\\\begin{pmatrix}C_3\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=4$$O problema foi reduzido para \$m=4\$e \$r=3\$. O maior valor de \$C_3\$que satisfaz as desigualdades \$\begin{pmatrix}C_3\\3\end{pmatrix}\leq4\$e \$C_3\lneq C_4\$deve ser encontrado. \$C_3\$é quatro:$$\begin{pmatrix}4\\3\end{pmatrix}+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=4\\4+\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=4\\\begin{pmatrix}C_2\\2\end{pmatrix}+\begin{pmatrix}C_1\\1\end{pmatrix}=0$$Qualquer combinação da forma \$\begin{pmatrix}n\\k\end{pmatrix}\$com \$n<k\$é zero, e assim \$C_2=1\$e \$C_1=0\$:$$\begin{pmatrix}1\\2\end{pmatrix}+\begin{pmatrix}0\\1\end{pmatrix}=0\\0+0=0\\0=0\checkmark$$
Observe que \$C_2\$não pode ser zero porque então \$C\$não aumentaria estritamente a menos que \$C_1\$foram negativos, o que não pode ser o caso devido à condição de que \$C\$consiste apenas em números inteiros não negativos. A solução é resumida com a declaração \$C=(0,1,4,6)\$(aqui, a indexação baseada em 1 é usada). O processo seguido aqui é garantido para produzir o correto \$C\$.
O desafio
Dado \$m\$e \$r\$, encontre os elementos de \$C\$.
Regras
Isso é código-golfe, então a resposta mais curta em bytes vence.
Assuma que apenas uma entrada válida será fornecida.
A entrada e a saída podem assumir qualquer forma que seja mais conveniente. Isso pode incluir a saída dos elementos de \$C\$em qualquer ordem, porque \$C\$estritamente aumenta e, portanto, a ordem real dos elementos é encontrada trivialmente ao classificá-los.
Termos cujas combinações resultam em zero, por exemplo \$C_2\$e \$C_1\$no exemplo, não pode ser negligenciado na saída.
Um programa teoricamente deveria funcionar para valores arbitrariamente grandes de \$m\$e \$r\$, mas ainda é aceitável se for limitado por restrições de memória.
Casos de teste
Aqui \$m\$é o primeiro número e \$r\$é o segundo e a saída começa com \$C_1\$.
In: 19 4
Out: 0 1 4 6
In: 0 4
Out: 0 1 2 3
In: 40000 6
Out: 6 8 9 11 12 20
In: 6 6
Out: 1 2 3 4 5 6
In: 6 5
Out: 0 1 2 3 6
In: 6 20
Out: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 (note 14 is skipped)
In: 6 1
Out: 6
Respostas
JavaScript (ES6), 95 93 86 82 bytes
Espera (r)(m).
r=>F=(m,x=r)=>r?(g=k=>!k||g(--k)*(k-x)/~k)(r)>m?[...F(m-g(r--,--x)),x]:F(m,x+1):[]
Experimente on-line!
Como?
função auxiliar
A função auxiliar \$g\$é usado para calcular:
$$\binom{x}{r}=\frac{x(x-1)\dots(x-r+1)}{r!}=\prod_{k=1}^{r}\frac{x-k+1}{k}$$
(g = k => // g is a recursive function taking k
!k // if k = 0, stop the recursion and return 1
|| // otherwise:
g(--k) // decrement k and do a recursive call with the updated value
* (k - x) // multiply the result by k - x
/ ~k // divide by -k - 1
// which is equivalent to g(k - 1) * (x - k + 1) / k
)(r) // initial call to g with k = r
Função principal
r => // r = requested number of combinations
F = (m, x = r) => // F is a recursive function taking the target number m
// and a counter x, initialized to r
r ? // if r is not equal to 0:
g(r) > m ? // if C(x, r) is greater than m:
[ ...F( // append the result of a recursive call to F:
m - g(r--, --x) // with m - C(x - 1, r) and r - 1
), // end of recursive call
x // append x (which was decremented above)
] //
: // else:
F(m, x + 1) // increment x until C(x, r) > m
: // else:
[] // stop the recursion
05AB1E , 13 11 bytes
∞<æIù.ΔācOQ
Entradas na ordem \$r,m\$.
Experimente online ou verifique todos os casos de teste .
Explicação:
∞ # Push an infinite positive list: [1,2,3,4,5,...]
< # Decrease it by 1 to include 0: [0,1,2,3,4,...]
æ # Get the powerset of this infinite list
Iù # Only leave sublists of a size equal to the first input `r`
.Δ # Find the first list which is truthy for:
ā # Push a list in the range [1,length] (without popping the list itself)
c # Get the binomial coefficient of the values at the same indices in the lists
O # Sum those
Q # And check if it's equal to the (implicit) second input `m`
# (after which the found list is output implicitly as result)
Gelatina , 12 bytes
Eu sinto que pode ser mais curto, possivelmente criando primeiro um produto externo usando a função binomial, \$m\$cþ\$r\$.
»Żœc⁸cJ$S⁼ɗƇ
Um programa completo aceitando \$r\$ e \$m\$ que imprime o resultado.
(Ou um Link diádico produzindo uma lista contendo o resultado único.)
Experimente on-line!
Como?
»Żœc⁸cJ$S⁼ɗƇ - Main Link: r, n
» - maximum (r,n)
Ż - zero range -> [0,1,2,...,max(r,n)]
⁸ - chain's left argument, r
œc - all (r-length) choices (of the zero range)
Ƈ - filter keep those for which:
ɗ - last three links as a dyad - f(selection, n)
$ - last two links as a monad - g(selection)
J - range of length -> [1,2,...,r]
c - binomial (vectorises) [s1C1, s2C2,...,srCr]
S - sum
⁼ - equals (n)?
- implicit print (a list containing a single element prints that element)
Python 3.8 (pré-lançamento) , 125 121 114 111 108 107 bytes
import math
c=math.comb
f=lambda n,r,k=0:n and(n<c(k+1,r)and f(n-c(k,r),r-1)+[k]or f(n,r,k+1))or[*range(r)]
Experimente on-line!
Explicação: Comece k=0e continue aumentando kdesde comb(k, r)que não exceda n. Atualize nde acordo. Uma vez que o valor atual de né 0, simplesmente retorne os primeiros rinteiros começando de 0.
R , 98 96 bytes
s=function(m,r,j=choose(1:(m+r),r))if(r)`if`(!m,1:r-1,c(s(m-max(j[j<=m]),r-1),max(which(j<=m))))
Experimente on-line!
Comentou:
choose_series=
s=function(m,r, # recursive function s
j=choose((m+r):1,r)) # j = all relevant values of choose(c,r)
if(r) # if r==0 don't return anything else
`if`(!m, # if m==0 ...
1:r-1, # ...just return the remaining r-series minus 1
c( # otherswise return ...
s( # recursive call to self, with
m- # new m = current m minus ...
max(j[j<=m]) # ... highest value of j less than or equal to m
,r-1), # new r = r-1;
((m+r):1)[j<=m][1] # appended to the highest value of c for which...
) # ...j is less than or equal to m
)
(mas, frustrantemente, minha abordagem aqui ainda sai mais do que uma porta de 84 bytes da abordagem de Arnauld ...)
Wolfram Language (Mathematica) , 92 bytes
(S=Select)[Subsets[S[0~Range~Max[a=#,b=#2],#~(B=Binomial)~b<a+1&],{b}],Tr@B[#,Range@b]==a&]&
Experimente on-line!
carvão , 39 bytes
ＮθＦ⮌ＥＮＥ⊕ιλ«≔Π⊕ιηＷ¬›Π⊕ι×θη≦⊕ι≧⁻÷ΠιηθＩ⟦⊟ι
Experimente on-line! O link é para a versão detalhada do código. Saídas em ordem decrescente. Explicação:
Ｎθ
Entrada m.
Ｆ⮌ＥＮＥ⊕ιλ«
Percorra os nintervalos [0..n-1], [0..n-2], ... [0, 1], [0]. Estes representam Cᵢde baixo para imas também o produto calcula para o termo binomial.n1Cᵢ!/(Cᵢ-i)!
≔Π⊕ιη
Pegue o produto do intervalo incrementado, que é apenas i!. Isto é usado para completar o cálculo do termo binomial.
Ｗ¬›Π⊕ι×θη≦⊕ι
Incremente o intervalo, incrementando efetivamente Cᵢ, até que o próximo termo binomial exceda m. (Não costumo incrementar um intervalo inteiro em carvão!)
≧⁻÷Πιηθ
Subtraia o termo binomial atual de m.
Ｉ⟦⊟ι
Saída Cᵢ(que é sempre o último elemento do intervalo) em sua própria linha.