عودة عدد صحيح عشوائي من الفاصل الزمني بناء على النتيجة الأخيرة والبذور

Question

لنفترض أن لدينا فاصل من الأعداد الصحيحة [أ، ب].أرغب في الحصول على وظيفة تقوم بإرجاع أعضاء عشوائي من داخل الفاصل الزمني، دون تكرار.بمجرد استكشاف جميع الأعضاء داخل الفاصل الزمني، ستبدأ الوظيفة في إرجاع نفس التسلسل الأول الأول مرة أخرى، بنفس الترتيب.

مثال: A= 1، B= 5

giveacodicetagpre.

سيكون من السهل تحقيقه من خلال خلط مجموعة من جميع العناصر بين A و B، وتكرارها بمجرد الانتهاء من الصفيف.ومع ذلك، فإن هذا سيستغرق الكثير من مساحة الذاكرة، وهذا غير مناسب لحالتي (قد يكون لدي ملايين العناصر).

بدلا من ذلك، فإن الوظيفة التي أود الحصول عليها ستكون أكثر أو أقل مثل هذا:

giveacodicetagpre.

أين:

giveacodicetagpre.

تختفي الخدعة بطريقة ما للحصول على رقم غير متكرر من الفاصل الزمني المبني فقط على العنصر الذي تم إرجاعه من قبل والبذور.في النهاية، ستصرف مثل قائمة دائرية عشوائية في تهيئةها، ولكن دون استخدام مساحة الذاكرة.

Answer 1

أقترح عليك اختيار التقليب العشوائي على النطاق $ [a، b] $ ، أي وظيفة الحفارة $ \ Pi: [A، B] \ إلى [A، B] $ . بعد ذلك، الحفاظ على العداد $ i $ يبدأ في $ i= $ ؛ في كل خطوة، إخراج $ \ Pi (i) $ ثم الزيادة $ i $ $ (التفاف حولها أن $ B + 1 $ يصبح $ $ ).

هناك طرق قياسية لتوليد هذا التقليب العشوائي في أدب التشفير: ابحث عن تشفير الحفاظ على التنسيق. البذور هي مفتاح التشفير. سوف تكون قادرا على حساب $ \ pi (i) $ في $ O (1) $ الوقت ووقت $ O (1) $ المساحة، لذلك يجب أن يكون هذا فعالا للغاية وتجنب الحاجة إلى الكثير من التخزين.

إذا كنت تصر على أن الإخراج التالي يجب أن يكون وظيفة الإخراج السابق، فيمكنك ترك $ g (i)= i + 1 $ (باستثناء ذلك < Span Class="حاوية الرياضيات"> $ g (b)= $ )، ثم دع $ f (i)=pi ^ {- 1} (g (\ pi (i)) $ ، حيث $ \ PI $ هو التقليب العشوائي المختار على النحو الوارد أعلاه. هذا سوف يعطيك بعد ذلك دورة عشوائية تكرار من خلال عناصر $ [a، b] $ في ترتيب عشوائي. المخرجات هي التسلسل $ f (a) ، f (f (a))، f (f (f (f (a)))، \ dots $ .