ตีกอล์ฟ \ $\mathbb{N}^n\to\mathbb{N}\$

Question

งานของคุณคือเขียนโปรแกรมที่ใช้ bijection \$\mathbb{N}^n\to\mathbb{N}\$สำหรับ\$n \ge 1\$. โปรแกรมของคุณควรใช้\$n\$ตัวเลขธรรมชาติเป็นอินพุตในวิธีการใด ๆที่ยอมรับได้ (รวมถึงการใช้เป็นค่าเดียว\$n\$ รายการองค์ประกอบ / อาร์เรย์) และส่งออกตัวเลขธรรมชาติที่ไม่ซ้ำกันสำหรับอินพุตที่เป็นไปได้ทั้งหมด

ในแง่ของคนธรรมดาอคติ \$\mathbb{N}^n\to\mathbb{N}\$ หมายถึง:

• รับ\$n\$ ตัวเลขธรรมชาติเป็นอินพุต
• แมปเหล่านี้\$n\$ จำนวนธรรมชาติไปยังเอาต์พุตจำนวนธรรมชาติเดียว
• สำหรับทุกอินพุตที่เป็นไปได้เอาต์พุตจะไม่ซ้ำกัน
• สำหรับทุกเอาต์พุตที่เป็นไปได้จะมีอินพุตซึ่งจะให้เอาต์พุตนั้น

ตัวอย่างเช่นฟังก์ชันการจับคู่ต้นเสียง \$\pi : \mathbb{N}^2\to\mathbb{N}\$ คือการคาดคะเนที่ใช้ตัวเลขธรรมชาติสองตัวและจับคู่แต่ละคู่กับจำนวนธรรมชาติที่ไม่ซ้ำกัน

คุณสามารถใช้ฟังก์ชัน bijective อะไรก็ได้ที่คุณต้องการตราบเท่าที่ได้รับการพิสูจน์แล้วว่าเป็น bijective สำหรับอินพุตที่เป็นไปได้ทั้งหมด โปรดใส่หลักฐานนี้ (โดยตรงหรือผ่านลิงค์) ในคำตอบของคุณ นี่คือโค้ดกอล์ฟดังนั้นโค้ดที่สั้นที่สุดในหน่วยไบต์จะชนะ

คุณอาจตัดสินใจว่าคุณต้องการใช้\$\mathbb{N} = \{1, 2, 3, \dots\}\$หรือ\$\mathbb{N} = \{0, 1, 2, \dots\}\$ตราบใดที่สิ่งนี้สอดคล้องกันสำหรับทุกคน\$n\$.

Answer 1

APL (Dyalog Unicode) , 13 10 ไบต์

(⊢+1⊥∘⍳+)/

ลองออนไลน์!

คล้ายกับคำตอบอื่น ๆ เนื่องจากการจับคู่ต้นเสียงเป็นแบบ bijective การประกอบ\$n-1\$ การจับคู่ต้นเสียงนั้นมีความหมายเชิงอคติเช่นกัน

(       )/  ⍝ reduce the input with following function
       +    ⍝ left argument + right argument
      ⍳     ⍝ the first left+right positive integers
   1⊥       ⍝ convert those from base 1 (sum)
 ⊢+         ⍝ + right argument

Answer 2

J , 8 ไบต์

,@|:&.#:

ลองออนไลน์! (เอาต์พุตเมทริกซ์ 10x10 สำหรับ f (A, B) และตัวเลขที่ต่อเนื่องกันสำหรับ n = 3)

โดยพื้นฐานแล้วใช้แนวคิดเริ่มต้นของนีลโดยรวมบิตโดยการกระจายอย่างสม่ำเสมอ (สำหรับ n = 3 บิตมาสก์สำหรับเอาต์พุตคือ… 1 2 3 1 2 3 1 2 3) แต่แทนที่จะขยับบิตเราใช้ประโยชน์จากรูปร่าง: แปลงแต่ละตัวเลขเป็นฐาน 2 และรายการแผ่นด้วยศูนย์ fe #: 2 3 8คือ

0 0 1 0
0 0 1 1
1 0 0 0

เปลี่ยนเมทริกซ์ด้วย|::

0 0 1
0 0 0
1 1 0
0 1 0

และ 'deshape' ด้วย,คือรวมแถวลงในรายการ: 0 0 1 0 0 0 1 1 0 0 1 0และแปลงกลับจากฐาน 2 &.#:เป็นตัวเลข: 562

Answer 3

เยลลี่ 6 ไบต์

น่าจะเป็น 6 byter ของ caird ...

+RS+ʋ/

ลองออนไลน์!

อย่างไร?

ใช้งานแอปพลิเคชันซ้ำ ๆ ของฟังก์ชันการจับคู่ต้นเสียง

แอปพลิเคชันเดียวคือ\$f(a,b)=\frac{1}{2}(a+b)(a+b+1)+b\$

แต่ทราบว่า\$\frac{1}{2}(a+b)(a+b+1)=\sum_{i=1}^{a+b}i\$

ดังนั้น\$f(a,b)=b+\sum_{i=1}^{a+b}i\$

+RS+ʋ/ - Link: list of non-negative integers
     / - reduce by:
    ʋ  -   last four links as a dyad - f(a,b)
+      -     add     -> a+b
 R     -     range   -> [1,2,3,...,a+b]
  S    -     sum     -> (a+b)(a+b+1)/2
   +   -     add (b) -> b+(a+b)(a+b+1)/2

Answer 4

Python 2 , 38 ไบต์

f=lambda a,*l:l and(a-~a<<f(*l))-1or a

ลองออนไลน์!

รับอินพุตแบบf(1,2,3)แยกส่วน

ใช้ฟังก์ชันการจับคู่\$p(a,b)=(2a+1)2^b\$. เราใช้ bit-shift <<bเพื่อย่อ*2**bและเขียนa-~aเพื่อบันทึกไบต์จาก2*a+1.

41 ไบต์

lambda l:reduce(lambda a,b:(a-~a<<b)-1,l)

ลองออนไลน์!

Answer 5

ถ่าน , 21 18 ไบต์

Ｗ⊖Ｌθ⊞θ⊖×⊕⊗⊟θＸ²⊟θＩθ

ลองออนไลน์! ตอนนี้ใช้ฟังก์ชันจับคู่ของ @ xnor คำตอบก่อนหน้า 21 ไบต์:

Ｗ⊖Ｌθ⊞θΣＥ²×⊕κ↨↨⊟貦⁴Ｉθ

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

Ｗ⊖Ｌθ

ทำซ้ำจนกว่าจะเหลือเพียงองค์ประกอบเดียว (เช่นลดขวา) ...

⊞θΣＥ²×⊕κ↨↨⊟貦⁴

แปลงสององค์ประกอบสุดท้ายเป็นฐาน 2 จากนั้นกลับจากฐาน 4 เพิ่มสององค์ประกอบหนึ่งในนั้นแล้วหาผลรวมผลักผลลัพธ์กลับไปที่รายการ สิ่งนี้เทียบเท่ากับการแทรกระหว่างบิต ฉันใช้ bijection นี้มากกว่าฟังก์ชั่นการจับคู่ต้นเสียงเนื่องจากต้องอ่านค่าแต่ละค่าเพียงครั้งเดียวจึงทำให้เป็นนักกอล์ฟในถ่าน

Ｉθ

แสดงผลลัพธ์สุดท้าย

Answer 6

Haskell , 27 ไบต์

foldr1(\a b->2^a*(2*b+1)-1)

ลองออนไลน์!

ใช้ bijection ที่แตกต่างจากฟังก์ชันจับคู่ Cantor จำนวนเต็มบวกทุกจำนวนสามารถแบ่งออกเป็นเลขยกกำลัง 2 เท่าของจำนวนคี่โดยไม่ซ้ำกันนั่นคือ\$2^a(2b+1)\$สำหรับจำนวนเต็มที่ไม่เป็นลบ\$a,b\$. การลบ 1 หมายความว่าเราได้จำนวนเต็มที่ไม่เป็นลบทั้งหมดรวมถึง 0

นี่คือตารางสำหรับ bijection สำหรับ\$a,b\$ จาก 0 ถึง 6:

  0   2   4   6   8  10  12 ...
  1   5   9  13  17  21  25
  3  11  19  27  35  43  51
  7  23  39  55  71  87 103
 15  47  79 111 143 175 207
 31  95 159 223 287 351 415
 63 191 319 447 575 703 831
 ...                        ...

Answer 7

เยลลี่ 7 ไบต์

+‘c2+µ/

ลองออนไลน์!

0 คือจำนวนธรรมชาติ

ดำเนินการจับคู่ต้นเสียงและลดรายการในช่วงนั้น

(เห็นได้ชัดว่ามีโซลูชัน 6 ไบต์ดังนั้นฉันจึงเศร้า)

Cantor Pairing เป็น bijective (ฉันไม่แน่ใจในการพิสูจน์ แต่ฉันคิดว่านี่เป็นที่รู้จักกันดี) ดังนั้นเนื่องจากองค์ประกอบของ bijections เป็น bijective จึงเป็น bijective ในกรณี edge ที่ n = 1 นี่คือเอกลักษณ์ดังนั้นจึงยังคงเป็น bijective

อย่างน้อยก็เป็นวิธีที่ฉันคิดว่าได้ผล โปรดแจ้งให้เราทราบหากคุณพบค่าที่ไม่ได้แมปหรือการชนกัน

Answer 8

JavaScript (ES6), 33 ไบต์

a[]การจับคู่ต้นเสียงในอาร์เรย์การป้อนข้อมูล

a=>a.reduce((x,y)=>y-(x+=y)*~x/2)

ลองออนไลน์!

Answer 9

05AB1E , 10 9 ไบต์

Å«+LOy+}н

ลองมันออนไลน์หรือตรวจสอบกรณีทดสอบทั้งหมด

พอร์ตของคำตอบ APLของ@ovs ดังนั้นอย่าลืมโหวตให้เขา!
-1 ไบต์ขอบคุณที่@ovs

ทางเลือก9 ไบต์ :

ćsvy+LOy+

ลองมันออนไลน์หรือตรวจสอบกรณีทดสอบบางมากขึ้น

คำอธิบาย:

Å«         # Cumulative right-reduce by (unfortunately keeping all intermediate steps):
  +        #  Add them together: a+b
   L       #  Pop and push a list in the range [a+b]
    O      #  Sum this list
     y+    #  Add a to it
 }н        # After the reduce-by, pop the list and leave just the first item
           # (after which it is output implicitly as result)

ć          # Extract head of the (implicit) input-list; pushing the remainder-list
           # and first item separated to the stack
 s         # Swap so the remainder-list is at the top
  v        # Loop over each integer `y` in this list:
   y+      #  Add the current integer `y` to the top value
     L     #  Pop and push a list in the range [1,n]
      O    #  Sum this list
       y+  #  And add `y` to it
           # (after the loop, the integer is output implicitly as result)

Answer 10

Haskell, 31 ไบต์

foldl1(\x y->(x+y)*(x+y+1)/2+y)

ลองออนไลน์!

Answer 11

Scala, 34 ไบต์

_.reduce((x,y)=>(x+y)*(x+y+1)/2+y)

ลองออนไลน์

Seq[Int] => Intฟังก์ชั่นที่ไม่ระบุชื่อประเภท ใช้การจับคู่ต้นเสียงกับสององค์ประกอบจนกว่าผลลัพธ์จะเป็นจำนวนเต็มเดียว

Answer 12

C (gcc) , ^{62 \$\cdots\$ 56} 55 ไบต์

บันทึกไบต์ขอบคุณceilingcat !!!

f(a,l)int*a;{l=l?*++a=*a-(*a+=a[1])*~*a/2,f(a,l-1):*a;}

ลองออนไลน์!

ป้อนอาร์เรย์ของจำนวนธรรมชาติและความยาวลบ\$1\$และส่งกลับจำนวนธรรมชาติที่ไม่ซ้ำกันโดยใช้แคนเทอร์จับคู่

Answer 13

แกลบ 7 ไบต์

FS+ȯΣḣ+

ลองออนไลน์!

การจับคู่ Cantor แบบเรียกซ้ำ (แนวทางเดียวกับคำตอบของ HyperNeutrino )

FS+ȯΣḣ+
F           # Fold over list (=recursively apply to pairs):
 S+ȯΣḣ+     # Cantor-pairing bijection:
 S          # Hook: combine 2 functions using same (first) argument
  +         # add first argument to
   ȯ        # combination of 2 3 functions:
    Σ       # sum of
     ḣ      # series from 1 up to
      +     # sum of first & second arguments

Answer 14

Retina , 59 ไบต์

.+
*
+`(_+)\1
$1@ @_ _ ^'@P`.+ N$`.
$.%`
¶

_
@_
+`_@
@__
_

ลองออนไลน์! คำอธิบาย:

.+
*
+`(_+)\1
$1@
@_
_

แปลงการป้อนข้อมูลเพื่อไบนารีใช้@สำหรับ0และสำหรับ_1

^'@P`.+

วางซ้ายทุกบรรทัด@ให้ยาวเท่ากัน

N$`. $.%`
¶

ย้ายและเข้าร่วมบรรทัด

_
@_
+`_@
@__
_

แปลงจากฐานสองเป็นฐานสิบ