Descomposición Combinatoria
En el cuerpo de este desafío, \$\begin{pmatrix}n\\k\end{pmatrix}\$se utiliza para representar el número de combinaciones de \$k\$elementos de \$n\$, también escrito como \$\frac{n!}{k!(n-k)!}\$o \$n\mathrm{C}r\$.
Cualquier entero no negativo \$m\$, para natural arbitrario (positivo) \$r\$, se puede escribir como una serie única de \$r\$combinaciones tales que$$m=\sum\limits_{i=1}^{r}\begin{pmatrix}C_i\\i\end{pmatrix}$$proporcionó la secuencia \$C\$ambos aumentan estrictamente (es decir, \$C_{\ell-1}\lneq C_\ell\$) y consiste únicamente en números enteros no negativos. \$C\$no es necesariamente único sin estas restricciones.
Ejemplo
Considere \$m=19\$y \$r=4\$. valores de \$C_4\$, \$C_3\$, \$C_2\$y \$C_1\$se debe encontrar para la ecuación$$19=\sum\limits_{i=1}^4\begin{pmatrix}C_i\\i\end{pmatrix}\\$$que se puede reescribir 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$$Comience por encontrar el valor más grande de \$C_4\$que satisface la desigualdad \$\begin{pmatrix}C_4\\4\end{pmatrix}\leq 19\$. \$C_4\$es 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$$El problema se ha reducido a \$m=4\$y \$r=3\$. El mayor valor de \$C_3\$que satisface las desigualdades \$\begin{pmatrix}C_3\\3\end{pmatrix}\leq4\$y \$C_3\lneq C_4\$debe ser encontrado \$C_3\$es cuatro:$$\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$$Cualquier combinación de la forma \$\begin{pmatrix}n\\k\end{pmatrix}\$con \$n<k\$es cero, entonces \$C_2=1\$y \$C_1=0\$:$$\begin{pmatrix}1\\2\end{pmatrix}+\begin{pmatrix}0\\1\end{pmatrix}=0\\0+0=0\\0=0\checkmark$$
Tenga en cuenta que \$C_2\$no puede ser cero porque entonces \$C\$no aumentaría estrictamente a menos que \$C_1\$eran negativos, lo que no puede ser el caso debido a la condición de que \$C\$consiste únicamente en números enteros no negativos. La solución se resume con la instrucción \$C=(0,1,4,6)\$(aquí, se utiliza la indexación basada en 1). El proceso seguido aquí está garantizado para producir el \ correcto$C\$.
El reto
dado \$m\$y \$r\$, encuentra los elementos de \$C\$.
Normas
Esto es code-golf, por lo que gana la respuesta más corta en bytes.
Suponga que solo se dará una entrada válida.
La entrada y la salida pueden asumir cualquier forma que sea más conveniente. Esto puede incluir la salida de los elementos de \$C\$en cualquier orden, porque \$C\$aumenta estrictamente, por lo que el orden real de los elementos se encuentra de manera trivial al ordenarlos.
Términos cuyas combinaciones dan como resultado cero, por ejemplo, \$C_2\$y \$C_1\$en el ejemplo, no se puede despreciar en la salida.
En teoría, un programa debería funcionar para valores arbitrariamente grandes de \$m\$y \$r\$, pero aún es aceptable si está limitado por restricciones de memoria.
Casos de prueba
Aquí \$m\$es el primer número y \$r\$es el segundo, y la salida comienza con \$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
Respuestas
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):[]
¡Pruébelo en línea!
¿Cómo?
función auxiliar
La función auxiliar \$g\$se utiliza 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
Función 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 en el orden \$r,m\$.
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
∞ # 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)
Jalea , 12 bytes
Siento que bien puede ser más corto, posiblemente creando primero un producto externo usando la función binomial, \$m\$cþ\$r\$.
»Żœc⁸cJ$S⁼ɗƇ
Un programa completo que acepta \$r\$ y \$m\$ que imprime el resultado.
(O un enlace diádico que produce una lista que contiene el resultado único).
¡Pruébelo en línea!
¿Cómo?
»Żœ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 (versión preliminar) , 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)]
¡Pruébelo en línea!
Explicación: Comience desde k=0y siga aumentando khasta comb(k, r)que no exceda n. Actualice en nconsecuencia. Una vez que el valor actual de nsea 0, simplemente devuelva los primeros renteros a partir 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))))
¡Pruébelo en línea!
Comentado:
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
)
(pero, frustrantemente, mi enfoque aquí todavía sale más largo que un puerto de 84 bytes del enfoque 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&]&
¡Pruébelo en línea!
Carbón , 39 bytes
ＮθＦ⮌ＥＮＥ⊕ιλ«≔Π⊕ιηＷ¬›Π⊕ι×θη≦⊕ι≧⁻÷ΠιηθＩ⟦⊟ι
¡Pruébelo en línea! El enlace es a la versión detallada del código. Salidas en orden descendente. Explicación:
Ｎθ
entrada m_
Ｆ⮌ＥＮＥ⊕ιλ«
Bucle sobre los nrangos [0..n-1], [0..n-2], ... [0, 1], [0]. Estos representan Cᵢdesde abajo hasta ipero también el producto se calcula para el término binomial.n1Cᵢ!/(Cᵢ-i)!
≔Π⊕ιη
Tome el producto del rango incrementado, que es solo i!. Se utiliza para completar el cálculo del término binomial.
Ｗ¬›Π⊕ι×θη≦⊕ι
Incremente el rango, incrementando efectivamente Cᵢ, hasta que el próximo término binomial exceda m. (¡No suelo incrementar un rango completo en Charcoal!)
≧⁻÷Πιηθ
Resta el término binomial actual de m.
Ｉ⟦⊟ι
Salida Cᵢ(que siempre es el último elemento del rango) en su propia línea.