Combinatorial Decomposition

Question

ในเนื้อหาของความท้าทายนี้\$\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\$ เป็นหก: $$\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\$ เป็นสี่: $$\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\$เป็นศูนย์ดังนั้น\$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\$ไม่สามารถเป็นศูนย์ได้เพราะงั้น\$C\$จะไม่เพิ่มขึ้นอย่างเคร่งครัดเว้นแต่\$C_1\$เป็นลบซึ่งไม่สามารถเป็นเช่นนั้นได้เนื่องจากเงื่อนไขที่\$C\$ประกอบด้วยจำนวนเต็มที่ไม่เป็นค่าลบเท่านั้น การแก้ปัญหาสรุปด้วยคำสั่ง\$C=(0,1,4,6)\$(ที่นี่ใช้การจัดทำดัชนีแบบ 1 ฐาน) กระบวนการที่ใช้ที่นี่มีการประกันเพื่อการผลิตที่ถูกต้อง\$C\$.

---

ความท้าทาย

ให้\$m\$และ\$r\$ค้นหาองค์ประกอบของ\$C\$.

กฎ

• นี่คือโค้ดกอล์ฟดังนั้นคำตอบที่สั้นที่สุดในหน่วยไบต์จะชนะ

• สมมติว่าจะได้รับเฉพาะอินพุตที่ถูกต้องเท่านั้น

• อินพุตและเอาต์พุตอาจถือว่ารูปแบบใดสะดวกที่สุด ซึ่งอาจรวมถึงการส่งออกองค์ประกอบของ\$C\$ตามลำดับใด ๆ เพราะ\$C\$ เพิ่มขึ้นอย่างเคร่งครัดดังนั้นลำดับที่แท้จริงขององค์ประกอบจะพบได้เล็กน้อยโดยการจัดเรียง

• คำศัพท์ที่ชุดค่าผสมประเมินเป็นศูนย์เช่น\$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

Answer 1

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

Answer 2

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)

Answer 3

เยลลี่ 12 ไบต์

^{ฉันรู้สึกว่ามันอาจจะสั้นกว่านี้ได้โดยการสร้างผลิตภัณฑ์ภายนอกโดยใช้ฟังก์ชันทวินามเป็นครั้งแรก\$m\$cþ\$r\$.}

»Żœc⁸cJ$S⁼ɗƇ

โปรแกรมเต็มรูปแบบยอมรับ\ $ r \ $และ\ $ m \ $ซึ่งพิมพ์ผลลัพธ์
(หรือลิงค์ dyadic ที่ให้รายการที่มีผลลัพธ์ที่ไม่ซ้ำกัน)

ลองออนไลน์!

อย่างไร?

»Żœ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)

Answer 4

งูหลาม 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 เพียงส่งคืนrจำนวนเต็มแรกเริ่มจาก 0

Answer 5

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
  )

(แต่น่าผิดหวังที่แนวทางของฉันที่นี่ยังคงออกมานานกว่าพอร์ต84 ไบต์ของแนวทางของ Arnauld ... )

Answer 6

ภาษา Wolfram (Mathematica) , 92 ไบต์

(S=Select)[Subsets[S[0~Range~Max[a=#,b=#2],#~(B=Binomial)~b<a+1&],{b}],Tr@B[#,Range@b]==a&]&

ลองออนไลน์!

Answer 7

ถ่าน 39 ไบต์

ＮθＦ⮌ＥＮＥ⊕ιλ«≔Π⊕ιηＷ¬›Π⊕ι×θη≦⊕ι≧⁻÷ΠιηθＩ⟦⊟ι

ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด ผลลัพธ์ตามลำดับจากมากไปหาน้อย คำอธิบาย:

Ｎθ

อินพุตm.

Ｆ⮌ＥＮＥ⊕ιλ«

ห่วงช่วงnช่วง[0..n-1], [0..n-2]... ,[0, 1] [0]เหล่านี้เป็นตัวแทนCᵢสำหรับiจากการnลงไป1แต่ยังคำนวณสินค้าCᵢ!/(Cᵢ-i)!ในระยะทวินาม

≔Π⊕ιη

i!ใช้ผลิตภัณฑ์ของช่วงเพิ่มขึ้นซึ่งเป็นเพียง ใช้เพื่อคำนวณระยะทวินามให้สมบูรณ์

Ｗ¬›Π⊕ι×θη≦⊕ι

เพิ่มช่วงได้อย่างมีประสิทธิภาพที่เพิ่มขึ้นจนระยะทวินามต่อไปจะเกินCᵢ m(ฉันไม่ค่อยได้เพิ่มช่วงทั้งหมดในชาร์โคล!)

≧⁻÷Πιηθ

mลบคำทวินามปัจจุบันจาก

Ｉ⟦⊟ι

เอาต์พุตCᵢ(ซึ่งเป็นองค์ประกอบสุดท้ายในช่วงเสมอ) ในบรรทัดของตัวเอง