Codejam2014
1
2
3
permutation ขนาด N เป็นลำดับของจำนวน N ตัว แต่ละตัวมีค่าระหว่าง 0 ถึง N-1 โดยที่แต่ละตัวปรากฏแค่หนึ่งครับ และสามารถปรากฏในลำดับใดก็ได้
มี permutation ขนาด N จำนวนมากมาย (มี N factorial แบบ แต่นั่นไม่จำเป็นสำหรับข้อนี้) บางทีเราต้องการสุ่มหยิบ permutation มาหนึ่งอัน และแน่นอนเราต้องการหยิบหนึ่งอันแบบ uniform (นั่นคือ ทุก ๆ permutation ขนาด N ต้องมีความน่าจะเป็นที่จะถูกเลือกเท่า ๆ กัน)
ด้านล่างเป็นโค้ดที่เป็นไปได้แบบหนึ่งที่จะทำงานนี้ (เราจะเรียกมันว่า good algorithm ต่อไป)
(ดูในโจทย์ภาษาอังกฤษ)
ในโค้ดด้านบน readint(a .. b) จะคืนค่าจำนวนเต็มที่สุ่มแบบ uniform จาก a ถึง b (รวม a และ b ด้วย)
นี่คืออัลกอริทึมนั้นถ้าอธิบายเป็นภาษาพูด: เราเริ่มที่ identity permutation จากนั้น for each k ตั้งแต่ 0 ถึง N-1 (inclusive) .....
นี่คือตัวอย่างสำหรับ N=4, เราเริ่มด้วย identity permutation:
0 1 2 3
(ดูต่อในโจทย์ภาษาอังกฤษ)
2 0 3 1
กระบวนการดังกล่าวจบลง และเราจะได้ random permutation
มีอัลกอริทึมอื่น ๆ อีกที่จะสร้าง random permutation อย่างไรก็ตาม มีอีกหลายอัลกอริทึมที่ดูคล้าย ๆ อัลกอริทึมด้านบน แต่ไม่ได้สร้าง random permutation ที่ uniform บาง permutation จะมีความน่าจะเป็นที่จะถูกสร้างมากกว่าอันอื่น
ด้านล่างเป็นอัลกอริทึมในกลุ่มดังกล่าว
