คำถามสนุก! เราสามารถตระหนักถึงขนาดพื้นที่ข้อความสูงสุดได้อย่างมีประสิทธิภาพ $(q-1)^t({n\atop t})$.
ให้เราเริ่มต้นด้วยกรณี $q=2$. เราต้องการสร้างสตริงความยาวบิต $n$ และแฮมมิ่งน้ำหนักเป๊ะ $t$. มี $C:=({n\atop t})$ สตริงดังกล่าวและเราต้องการแมปข้อความจำนวนเต็มจากช่วงเวลา $[0,C-1]$ ชุดนี้สองฝ่าย ชุดของสตริงบิตสอดคล้องกับ การรวมกัน (โดยเฉพาะ $t$- ผลรวมของจำนวนเต็ม 0 ถึง $n-1$). เราสามารถเขียนสตริงของเราใหม่เป็นลำดับที่ลดลงอย่างเข้มงวดของ $t$ ค่า $n-1\ge c_t>c_{t-1}>\ldots>c_1\ge 0$ โดยเขียนดัชนีตำแหน่งของเลข 1
ตอนนี้ ทฤษฎีบททางคณิตศาสตร์อันสวยหรูที่ Knuth กล่าวถึง Ernesto Pascal นักคณิตศาสตร์ในศตวรรษที่ 19 กล่าวว่าตัวเลขทุกตัว $N$ สามารถเป็นตัวแทนใน ระบบจำนวนเชิงผสม
$$N=\left({c_t\atop t}\right)+\cdots+\left({c_1\atop 1}\right)$$
และขั้นตอนการเรียงลำดับนี้ผ่านการรวมกันคือลำดับคำศัพท์ (สำหรับจุดประสงค์ของเรา อันดับแรก $({n\atop t})$ รายการน้ำหนักรายการ $t$ สายยาว $n$). ดังนั้นถ้าเรามีจำนวนเต็ม $N\ใน [0,C-1]$ เราสามารถใช้อัลกอริทึมโลภเพื่อกู้คืน $N$น้ำหนัก $t$ สตริงไบนารีที่กำหนดโดยระบบจำนวนเชิงผสม นี่คือรหัสเทียมบางส่วน:
เริ่มต้น i:=n-1, j:=t, ส่วนที่เหลือ=N
ในขณะที่ฉัน>=0
ถ้าทวินาม(i,j) > ส่วนที่เหลือ
ตั้งค่าบิต i ของสตริงเป็น 0
อื่น
ตั้งค่าบิต i ของสตริงเป็น 1
เจ--
ส่วนที่เหลือ -= ทวินาม (i,j)
ผม--
แผนที่ย้อนกลับตรงไปตรงมา
ตัวอย่างเช่นกับ $n=10$, $t=3$ มีชุดค่าผสมที่เป็นไปได้ 120 ชุด ให้เราหาชุดที่ 17 (นับ 0 ขึ้นไป) ก่อนอื่นเราจะหาจำนวนจัตุรมุขที่เล็กที่สุดไม่เกิน 17; นี่คือ $({5\atop 3})=10$; เราทำเครื่องหมายจุดที่ 5 และเหลืออีก 7 ตอนนี้เราพบจำนวนสามเหลี่ยมที่เล็กที่สุดไม่เกิน 7; นี่คือ $({4\atop 2})=6$; เราทำเครื่องหมายจุดที่ 4 และเหลืออีก 1 ตอนนี้เราพบว่าจำนวนที่น้อยที่สุดไม่เกิน 1; นี้ $({1\atop 1})=1$; เราทำเครื่องหมายจุดที่ 1 และไม่เหลืออะไรเลย สตริงของเราคือ 0000110010
. ถ้าเราได้รับสตริงที่เราคำนวณ $({5\atop 3})+({4\atop 2})+({1\atop 1})=10+6+1=17$.
สำหรับตัวอักษรทั่วไป เราสามารถใช้กระบวนการข้างต้นเพื่อสร้างตำแหน่งข้อผิดพลาด จากนั้นเลือกจาก $q-1$ ค่าความผิดพลาดที่เป็นไปได้สำหรับแต่ละตำแหน่ง ให้อย่างเป็นรูปธรรม $M=C(q-1)^t$ เป็นขนาดของพื้นที่ข้อความของเรา ได้รับข้อความ $m\in[0,M-1]$ เราปล่อยให้ $N=[m/(q-1)^t]$ ดังนั้น $N\in[0,C-1]$ และสร้างรายการสถานที่ตามด้านบน เราก็ปล่อยให้ $B=m\mod{(q-1)^t}$ และเขียน $B$ เป็น ก $t$- เลขฐาน $(q-1)$ (ให้เลขศูนย์นำหน้า) และกำหนดค่าหลัก +1 ให้กับแต่ละตำแหน่ง แผนที่ย้อนกลับนั้นตรงไปตรงมาอีกครั้ง
ตัวอย่างเช่น สมมติว่าเรามีตัวอักษรทศนิยมและพิจารณาสตริงที่มีความยาว 10 โดยมีข้อผิดพลาด 3 รายการ มี 120*729=87480 ข้อความที่เป็นไปได้; ให้เราหา 12707 เราพบว่า $N=[12707/729]=17$ และสร้างสตริงบิตเดียวกันกับด้านบน เราพบว่า $B=12707\mod{729}=314$ ซึ่งก็คือ 378 ในฐาน 9 ข้อความของเราแปลงเป็นสตริงข้อผิดพลาด 0000480090
. อีกครั้งถ้าเราได้รับสตริงนี้ เราจะดึงตัวเลขที่ไม่ใช่ศูนย์ออกมาตามลำดับและลบออกจากแต่ละหลักเพื่อให้เลขฐาน 9 เป็น 378 เพื่อให้ $B=314$ เราก็รู้เช่นเดียวกัน $N=17$ จากตำแหน่งข้อผิดพลาดและสามารถคำนวณได้ $m=729N+B=12707$.
บทที่ 7.2.1.3 "การสร้างชุดค่าผสมทั้งหมด" ของ "ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์" ขั้นสุดท้ายของ Donald Knuth เป็นบัญชีที่ยอดเยี่ยม ครอบคลุม (แม้ว่าจะเสียสมาธิ) ของอัลกอริทึมอื่นๆ สำหรับการสร้างชุดค่าผสม