조합 분해
이 도전의 본문에서 \$\begin{pmatrix}n\\k\end{pmatrix}\$표현하기 위해 사용되는 조합의 수 의를 \$k\$\의 요소$n\$, 또한 \$\frac{n!}{k!(n-k)!}\$또는 \$n\mathrm{C}r\$.
음이 아닌 정수 \$m\$, 임의의 자연 (긍정적) \$r\$, \ 의 고유 한 시리즈 로 쓸 수 있습니다.$r\$그와 같은 조합$$m=\sum\limits_{i=1}^{r}\begin{pmatrix}C_i\\i\end{pmatrix}$$시퀀스 제공 \$C\$둘 다 엄격하게 증가합니다 (예 : \$C_{\ell-1}\lneq C_\ell\$)이며 음이 아닌 정수로만 구성됩니다. \$C\$ 이러한 제한 없이는 반드시 고유 한 것은 아닙니다.
예
고려 \$m=19\$및 \$r=4\$. \의 값$C_4\$, \$C_3\$, \$C_2\$및 \$C_1\$ 방정식에 대해 찾아야합니다. $$19=\sum\limits_{i=1}^4\begin{pmatrix}C_i\\i\end{pmatrix}\\$$ 다음과 같이 다시 작성할 수 있습니다. $$\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$$\ 의 가장 큰 값을 찾아서 시작하십시오.$C_4\$불평등을 만족시키는 \$\begin{pmatrix}C_4\\4\end{pmatrix}\leq 19\$. \$C_4\$ 6입니다. $$\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$$문제가 \$m=4\$및 \$r=3\$. \ 의 가장 큰 가치$C_3\$불평등을 충족시키는 \$\begin{pmatrix}C_3\\3\end{pmatrix}\leq4\$및 \$C_3\lneq C_4\$찾아야합니다. \$C_3\$ 4입니다 : $$\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$$\ 형식의 모든 조합$\begin{pmatrix}n\\k\end{pmatrix}\$와 \$n<k\$0이므로 \$C_2=1\$및 \$C_1=0\$: $$\begin{pmatrix}1\\2\end{pmatrix}+\begin{pmatrix}0\\1\end{pmatrix}=0\\0+0=0\\0=0\checkmark$$
그 주 \$C_2\$다음이 0이기 때문에 할 수 없다 \$C\$엄격하게하지 않는 한 증가하지 않을 \$C_1\$부정적입니다. 이는 \$C\$음이 아닌 정수로만 구성됩니다. 솔루션은 \$C=(0,1,4,6)\$(여기서는 1 기반 인덱싱이 사용됩니다). 여기에 따르는 프로세스는 올바른 \$C\$.
도전
주어진 \$m\$및 \$r\$, \ 의 요소 찾기$C\$.
규칙
이것은 코드 골프 이므로 바이트 단위의 가장 짧은 답변이 이깁니다.
유효한 입력 만 제공된다고 가정합니다.
입력 및 출력은 가장 편리한 형식을 가정 할 수 있습니다. 여기에는 \ 의 요소 출력이 포함될 수 있습니다.$C\$순서에 관계없이 \$C\$ 엄격하게 증가하므로 요소의 실제 순서는 정렬하여 쉽게 찾을 수 있습니다.
조합이 0으로 평가되는 용어, 예 : \$C_2\$및 \$C_1\$ 예에서, 출력에서 무시할 수 없습니다.
프로그램은 이론적으로 \의 임의의 큰 값에 대해 작동해야합니다.$m\$및 \$r\$이지만 메모리 제약에 의해 제한되는 경우 여전히 허용됩니다.
테스트 케이스
여기 \$m\$첫 번째 숫자이고 \$r\$두 번째이고 출력은 \로 시작합니다.$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
답변
JavaScript (ES6), 95 93 86 82 바이트
기대 (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):[]
온라인으로 시도하십시오!
어떻게?
도우미 기능
도우미 기능 \$g\$ 다음을 계산하는 데 사용됩니다.
$$\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
주요 기능
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 바이트
∞<æIù.ΔācOQ
순서로 입력 \$r,m\$.
온라인으로 시도 하거나 모든 테스트 사례를 확인하십시오 .
설명:
∞ # 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)
젤리 , 12 바이트
I는 물론 제 이항 함수를 사용하여 외부 생성물을 생성함으로써 가능하게 짧아있을 수 느낌 \$m\$cþ\$r\$.
»Żœc⁸cJ$S⁼ɗƇ
결과를 인쇄하는 \ $ r \ $ 및 \ $ m \ $ 를 허용하는 전체 프로그램 .
(또는 고유 한 결과를 포함하는 목록을 생성하는 이원 적 링크.)
온라인으로 시도하십시오!
어떻게?
»Żœ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)
파이썬 3.8 (시험판) , 125 (121) 114 111 108 107 바이트
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)]
온라인으로 시도하십시오!
설명 : 시작에서 k=0와 것은 계속 증가 k긴만큼 comb(k, r)초과하지 않습니다 n. n그에 따라 업데이트하십시오 . 의 현재 값 n이 0이면 0 r부터 시작 하는 첫 번째 정수 를 반환하면 됩니다.
R , 98 96 바이트
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))))
온라인으로 시도하십시오!
댓글 :
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
)
(그러나 실망 스럽게도 여기에서의 접근 방식 은 Arnauld의 접근 방식의 84 바이트 포트 보다 더 오래 나옵니다 ...)
Wolfram 언어 (Mathematica) , 92 바이트
(S=Select)[Subsets[S[0~Range~Max[a=#,b=#2],#~(B=Binomial)~b<a+1&],{b}],Tr@B[#,Range@b]==a&]&
온라인으로 시도하십시오!
Charcoal , 39 바이트
ＮθＦ⮌ＥＮＥ⊕ιλ«≔Π⊕ιηＷ¬›Π⊕ι×θη≦⊕ι≧⁻÷ΠιηθＩ⟦⊟ι
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 내림차순으로 출력합니다. 설명:
Ｎθ
입력 m.
Ｆ⮌ＥＮＥ⊕ιλ«
오버 루프 n범위 [0..n-1], [0..n-2], ... [0, 1], [0]. 이 대표 Cᵢ에 대한 i에서 n아래로 1뿐만 아니라 제품을 계산 Cᵢ!/(Cᵢ-i)!이항 기간 동안.
≔Π⊕ιη
증가 된 범위의 곱을 취하십시오 i!. 이항 항의 계산을 완료하는 데 사용됩니다.
Ｗ¬›Π⊕ι×θη≦⊕ι
Cᵢ다음 이항 항이를 초과 할 때까지 범위를 증가시켜 효과적으로 증가시킵니다 m. (나는 종종 Charcoal에서 전체 범위를 증가시키지 않습니다!)
≧⁻÷Πιηθ
에서 현재 이항 항을 뺍니다 m.
Ｉ⟦⊟ι
Cᵢ자체 행에 출력 (항상 범위의 마지막 요소).