Decomposizione combinatoria
Nel corpo di questa sfida, \$\begin{pmatrix}n\\k\end{pmatrix}\$è usato per rappresentare il numero di combinazioni di \$k\$elementi di \$n\$, scritto anche come \$\frac{n!}{k!(n-k)!}\$o \$n\mathrm{C}r\$.
Qualsiasi numero intero non negativo \$m\$, per arbitrario naturale (positivo) \$r\$, può essere scritto come un'unica serie di \$r\$combinazioni tali che$$m=\sum\limits_{i=1}^{r}\begin{pmatrix}C_i\\i\end{pmatrix}$$fornito la sequenza \$C\$entrambi strettamente aumenta (cioè \$C_{\ell-1}\lneq C_\ell\$) e consiste esclusivamente di numeri interi non negativi. \$C\$non è necessariamente unico senza queste restrizioni.
Esempio
Considera \$m=19\$e \$r=4\$. Valori di \$C_4\$, \$C_3\$, \$C_2\$e \$C_1\$deve essere trovato per l'equazione$$19=\sum\limits_{i=1}^4\begin{pmatrix}C_i\\i\end{pmatrix}\\$$che può essere riscritta come$$\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$$Inizia trovando il valore più grande di \$C_4\$che soddisfa la disuguaglianza \$\begin{pmatrix}C_4\\4\end{pmatrix}\leq 19\$. \$C_4\$è sei:$$\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$$Il problema è stato ridotto a \$m=4\$e \$r=3\$. Il valore più grande di \$C_3\$che soddisfa le disuguaglianze \$\begin{pmatrix}C_3\\3\end{pmatrix}\leq4\$e \$C_3\lneq C_4\$deve essere trovato. \$C_3\$è quattro:$$\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$$Qualsiasi combinazione della forma \$\begin{pmatrix}n\\k\end{pmatrix}\$con \$n<k\$è zero, quindi \$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$$
Nota che \$C_2\$non può essere zero perché allora \$C\$non aumenterebbe strettamente a meno che \$C_1\$erano negativi, il che non può essere il caso a causa della condizione che \$C\$consiste esclusivamente di numeri interi non negativi. La soluzione è riassunta con l'affermazione \$C=(0,1,4,6)\$(qui viene utilizzata l'indicizzazione in base 1). Il processo qui seguito è garantito per produrre il corretto \$C\$.
La sfida
Dato \$m\$e \$r\$, trova gli elementi di \$C\$.
Regole
Questo è code-golf, quindi vince la risposta più breve in byte.
Si supponga che verrà fornito solo un input valido.
L'input e l'output possono assumere qualsiasi forma sia più conveniente. Ciò può includere l'output degli elementi di \$C\$in qualsiasi ordine, perché \$C\$aumenta strettamente e quindi l'effettivo ordine degli elementi si trova banalmente ordinandoli.
Termini le cui combinazioni valgono zero, ad esempio \$C_2\$e \$C_1\$nell'esempio, non può essere trascurato nell'output.
Un programma dovrebbe teoricamente funzionare per valori arbitrariamente grandi di \$m\$e \$r\$, ma è comunque accettabile se è limitato dai vincoli di memoria.
Casi test
Qui \$m\$è il primo numero e \$r\$è il secondo e l'output inizia 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
Risposte
JavaScript (ES6), 95 93 86 82 byte
Si aspetta (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):[]
Provalo online!
Come?
Funzione di aiuto
La funzione di supporto \$g\$viene utilizzato per calcolare:
$$\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
Funzione 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 byte
∞<æIù.ΔācOQ
Ingressi nell'ordine \$r,m\$.
Provalo online o verifica tutti i casi di test .
Spiegazione:
∞ # 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 byte
Sento che potrebbe essere più breve, possibilmente creando prima un prodotto esterno usando la funzione binomiale, \$m\$cþ\$r\$.
»Żœc⁸cJ$S⁼ɗƇ
Un programma completo che accetta \$r\$ e \$m\$ che stampa il risultato.
(O un collegamento diadico che produce un elenco contenente il risultato univoco.)
Provalo online!
Come?
»Żœ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 (versione preliminare) , 125 121 114 111 108 107 byte
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)]
Provalo online!
Spiegazione: inizia da k=0e continua ad aumentare kfinché comb(k, r)non supera n. Aggiorna di nconseguenza. Una volta che il valore corrente di nè 0, è sufficiente restituire i primi rnumeri interi a partire da 0.
R , 98 96 byte
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))))
Provalo online!
Commentato:
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
)
(ma, in modo frustrante, il mio approccio qui risulta ancora più lungo di un porting di 84 byte dell'approccio di Arnauld ...)
Wolfram Language (Mathematica) , 92 byte
(S=Select)[Subsets[S[0~Range~Max[a=#,b=#2],#~(B=Binomial)~b<a+1&],{b}],Tr@B[#,Range@b]==a&]&
Provalo online!
Carboncino , 39 byte
ＮθＦ⮌ＥＮＥ⊕ιλ«≔Π⊕ιηＷ¬›Π⊕ι×θη≦⊕ι≧⁻÷ΠιηθＩ⟦⊟ι
Provalo online! Il collegamento è alla versione dettagliata del codice. Uscite in ordine decrescente. Spiegazione:
Ｎθ
Ingresso m.
Ｆ⮌ＥＮＥ⊕ιλ«
Passa sopra gli nintervalli [0..n-1], [0..n-2], ... [0, 1], [0]. Questi rappresentano Cᵢda giù a ima anche il prodotto calcola per il termine binomiale.n1Cᵢ!/(Cᵢ-i)!
≔Π⊕ιη
Prendi il prodotto dell'intervallo incrementato, che è solo i!. Questo è usato per completare il calcolo del termine binomiale.
Ｗ¬›Π⊕ι×θη≦⊕ι
Incrementa l'intervallo, incrementando effettivamente Cᵢ, fino a quando il prossimo termine binomiale supererà m. (Non riesco spesso ad incrementare un'intera gamma in Charcoal!)
≧⁻÷Πιηθ
Sottrai il termine binomiale corrente da m.
Ｉ⟦⊟ι
Output Cᵢ(che è sempre l'ultimo elemento dell'intervallo) sulla propria riga.