Décomposition combinatoire
Dans le corps de ce défi, \$\begin{pmatrix}n\\k\end{pmatrix}\$est utilisé pour représenter le nombre de combinaisons de \$k\$éléments de \$n\$, également écrit comme \$\frac{n!}{k!(n-k)!}\$ou \$n\mathrm{C}r\$.
Tout entier non négatif \$m\$, pour naturel arbitraire (positif) \$r\$, peut être écrit comme une suite unique de \$r\$combinaisons telles que$$m=\sum\limits_{i=1}^{r}\begin{pmatrix}C_i\\i\end{pmatrix}$$fourni la séquence \$C\$les deux augmentent strictement (c'est-à-dire \$C_{\ell-1}\lneq C_\ell\$) et se compose uniquement d'entiers non négatifs. \$C\$n'est pas nécessairement unique sans ces restrictions.
Exemple
Considérez \$m=19\$et \$r=4\$. Valeurs de \$C_4\$, \$C_3\$, \$C_2\$et \$C_1\$doit être trouvé pour l'équation$$19=\sum\limits_{i=1}^4\begin{pmatrix}C_i\\i\end{pmatrix}\\$$qui peut être réécrit comme$$\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$$Commencez par trouver la plus grande valeur de \$C_4\$qui satisfait l'inégalité \$\begin{pmatrix}C_4\\4\end{pmatrix}\leq 19\$. \$C_4\$est six :$$\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$$Le problème a été réduit à \$m=4\$et \$r=3\$. La plus grande valeur de \$C_3\$qui satisfait les inégalités \$\begin{pmatrix}C_3\\3\end{pmatrix}\leq4\$et \$C_3\lneq C_4\$doit être trouvé. \$C_3\$est quatre :$$\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$$Toute combinaison de la forme \$\begin{pmatrix}n\\k\end{pmatrix}\$avec \$n<k\$est nul, et donc \$C_2=1\$et \$C_1=0\$:$$\begin{pmatrix}1\\2\end{pmatrix}+\begin{pmatrix}0\\1\end{pmatrix}=0\\0+0=0\\0=0\checkmark$$
Notez que \$C_2\$ne peut pas être zéro car alors \$C\$n'augmenterait strictement que si \$C_1\$étaient négatifs, ce qui ne peut pas être le cas en raison de la condition que \$C\$se compose uniquement d'entiers non négatifs. La solution est résumée par l'instruction \$C=(0,1,4,6)\$(ici, l'indexation de base 1 est utilisée). Le processus suivi ici est garanti pour produire le bon \$C\$.
Le défi
Étant donné \$m\$et \$r\$, trouver les éléments de \$C\$.
Règles
C'est du code-golf donc la réponse la plus courte en octets l'emporte.
Supposons que seule une entrée valide sera donnée.
L'entrée et la sortie peuvent prendre la forme la plus pratique. Cela peut inclure la sortie des éléments de \$C\$dans n'importe quel ordre, car \$C\$augmente strictement et ainsi l'ordre réel des éléments est trivialement trouvé en les triant.
Termes dont les combinaisons sont évaluées à zéro, par exemple \$C_2\$et \$C_1\$dans l'exemple, ne peut pas être négligé en sortie.
Un programme devrait théoriquement fonctionner pour des valeurs arbitrairement grandes de \$m\$et \$r\$, mais reste acceptable s'il est limité par des contraintes de mémoire.
Cas de test
Ici \$m\$est le premier nombre et \$r\$est le second, et la sortie commence par \$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
Réponses
JavaScript (ES6), 95 93 86 82 octets
Attend (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):[]
Essayez-le en ligne !
Comment?
Fonction d'assistance
La fonction d'assistance \$g\$sert à calculer :
$$\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
Fonction principale
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 octets
∞<æIù.ΔācOQ
Entrées dans l'ordre \$r,m\$.
Essayez-le en ligne ou vérifiez tous les cas de test .
Explication:
∞ # 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)
Gelée , 12 octets
I feel there may well be shorter, possibly by first creating an outer-product using the binomial function, \$m\$cþ\$r\$.
»Żœc⁸cJ$S⁼ɗƇ
A full-program accepting \$r\$ and \$m\$ which prints the result.
(Or a dyadic Link yielding a list containing the unique result.)
Try it online!
How?
»Żœ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 (pre-release), 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)]
Try it online!
Explanation: Start from k=0 and keep increasing k as long as comb(k, r) does not exceed n. Update n accordingly. Once the current value of n is 0, simply return the first r integers starting from 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))))
Try it online!
Commented:
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
)
(but, frustratingly, my approach here still comes-out longer than an 84 byte port of Arnauld's approach...)
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&]&
Try it online!
Charcoal, 39 bytes
ＮθＦ⮌ＥＮＥ⊕ιλ«≔Π⊕ιηＷ¬›Π⊕ι×θη≦⊕ι≧⁻÷ΠιηθＩ⟦⊟ι
Try it online! Link is to verbose version of code. Outputs in descending order. Explanation:
Ｎθ
Input m.
Ｆ⮌ＥＮＥ⊕ιλ«
Loop over the n ranges [0..n-1], [0..n-2], ... [0, 1], [0]. These represent Cᵢ for i from n down to 1 but also the product calculates Cᵢ!/(Cᵢ-i)! for the binomial term.
≔Π⊕ιη
Take the product of the incremented range, which is just i!. This is used to complete the calculation of the binomial term.
Ｗ¬›Π⊕ι×θη≦⊕ι
Increment the range, effectively incrementing Cᵢ, until the next binomial term would exceed m. (I don't often get to increment a whole range in Charcoal!)
≧⁻÷Πιηθ
Subtract the current binomial term from m.
Ｉ⟦⊟ι
Output Cᵢ (which is always the last element in the range) on its own line.