สับเปลี่ยนเพื่อให้ครอบคลุมการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมด

วัตถุสุ่มในกรอบงาน. NET รับจำนวนเต็ม 32 บิตเป็นข้อมูลเริ่มต้น ซึ่งหมายความว่าอัลกอริธึมการสับเปลี่ยนใด ๆ ที่ใช้วัตถุ Random นั้นถูกจำกัดไว้ที่ (สูงสุด) 4 พันล้านครั้งในการสับเปลี่ยนที่เป็นไปได้ (สมมติว่าการสับเปลี่ยนถูกกำหนดไว้ตามลำดับการสุ่ม ซึ่งฉันไม่สามารถจินตนาการได้ว่าทำไมมันถึงไม่เป็นเช่นนั้น) ซึ่งหมายความว่าเมื่อคอลเลกชันมีองค์ประกอบเกิน 13 รายการ รับประกันว่าการสับเปลี่ยนจะไม่ครอบคลุมการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมด เมื่อขนาดคอลเลกชันเพิ่มขึ้นจากขนาดนี้ ชุดย่อยของการเรียงสับเปลี่ยนที่เป็นไปได้ที่ครอบคลุมโดยการสับเปลี่ยนก็ไม่มีนัยสำคัญมากขึ้นเรื่อยๆ

4 พันล้านเป็นตัวเลขที่มาก (โดยส่วนตัว) แต่ถ้าคุณสร้างการเรียงสับเปลี่ยน "สุ่ม" หลายครั้งของคอลเลกชัน โอกาสที่การซ้ำจะมีมากกว่าที่ควรจะเป็นมาก (โดยเฉพาะอย่างยิ่งเมื่อคุณพิจารณาหลักการวันเกิดที่ขัดแย้งกัน / หลุมนกพิราบ)

มีวิธีง่ายๆ ใดบ้างที่ไม่เกี่ยวข้องกับฉันใช้เครื่องสร้างตัวเลขสุ่มของตัวเอง?


person Patrick M    schedule 01.07.2014    source แหล่งที่มา
comment
น่าสนใจ ดังนั้นความคุ้มครองกรณีที่ดีที่สุดคือ 4bil^n โดยที่ n คือจำนวนครั้งที่ฉันสับเปลี่ยน ปัญหาเดียวคือถ้าสับเปลี่ยนเร็วมาก ฉันอาจต้องนอนสักหนึ่งมิลลิวินาทีเพื่อให้แน่ใจว่าเมล็ดจะแตกต่างออกไป   -  person Patrick M    schedule 01.07.2014
comment
คุณสามารถลองใช้ API ออนไลน์ของ Random.org เพื่อสร้างแบบสุ่มได้ หากแอป/โปรเจ็กต์ของคุณเหมาะสม แค่สองเซ็นต์ของฉัน   -  person Lexicon    schedule 01.07.2014
comment
หากคุณใช้สิ่งนี้เพื่อเช่น เพื่อวัตถุประสงค์ในการเล่นเกม คุณควรเปลี่ยนไปใช้ RNG ที่ปลอดภัยแบบเข้ารหัส   -  person Damien_The_Unbeliever    schedule 01.07.2014
comment
แบ่งและพิชิต: int digitNum = 10; ยาว l = 0; สุ่ม r = สุ่มใหม่ (DateTime.Now.Millisecond); สำหรับ (int i = 0; i ‹ digitNum; i++) l += r.Next(0, 9) * (long)Math.Pow((double)10, (double)i);   -  person Johnny    schedule 01.07.2014
comment
โปรดทราบว่า DateTime.Millisecond อาจเปลี่ยนแปลงทุกๆ สองสามมิลลิวินาทีเท่านั้น ขึ้นอยู่กับระบบ   -  person Matthew Watson    schedule 01.07.2014
comment
อัลกอริธึมการสับเปลี่ยนของ Fisher–Yates จะไม่แก้ปัญหาของคุณหรือไม่   -  person Felice Pollano    schedule 01.07.2014
comment
ericlippert.com/2013/05/06/procing-permutations-part -เจ็ด. ลองคิดดู คุณควรอ่านทั้งซีรีส์เริ่มต้นที่ ericlippert .com/2013/04/15/producting-permutations-part-one ในนั้น เขาแสดงวิธีเปลี่ยนตัวเลขสุ่มเป็นการเรียงสับเปลี่ยน   -  person Jim Mischel    schedule 01.07.2014


คำตอบ (2)


ฉันไม่แนะนำให้สร้างตัวสร้างตัวเลขสุ่ม (RNG) ของคุณเอง ทฤษฎีเบื้องหลังพวกเขาค่อนข้างมั่นคง หากคุณต้องการบางสิ่งที่ 'สุ่มมากขึ้น' คุณจะต้องใช้ RNG ที่ปลอดภัยแบบเข้ารหัส วิธีใช้ตัวสร้างเริ่มต้นที่มาจากเฟรมเวิร์ก .Net:

ใช้ System.Security.Cryptography;

ตัวสร้าง var = RandomNumberGenerator.Create();

คุณสามารถใช้สิ่งนี้เพื่อรับไบต์สุ่มซึ่งคุณสามารถแปลงเป็น int หรือค่าประเภทอื่นได้

person Ananke    schedule 01.07.2014

คุณสามารถใช้ พอร์ตของ Mersenne Twister ถึง C# MT19937 มีพื้นที่สถานะ 19937 บิต และถึงแม้คุณสามารถเลือกที่จะทำการ seed ด้วย int เดียว แต่การ seed แบบเต็มสถานะก็สามารถใช้ได้ หากคุณมีแหล่งเอนโทรปีที่เหมาะสมเพื่อป้อนมัน

person pjs    schedule 01.07.2014