تبحث عن خوارزمية للبصق على سلسلة من الأرقام في ترتيب عشوائي (pseudo)

Question

افترض أن لدي سلسلة من الأرقام: {n، n + 1، n + 2، ... N + M}

دون تخزين الأرقام في وقت مبكر، أريد إنشاء وظيفة F ()، والتي تعطى التسلسل {1،2،3، ... M} سوف بصق مجموعة الأصلية في ترتيب عشوائي عشوائي (أو على الأقل عشوائية زائفة) وبعد

على سبيل المثال افترض التسلسل الخاص بي هو {10، 11، 12، 13، 14، 15، 16، 17}

 F (1) يمكن أن تسفر عن 14 و (2) يمكن أن تسفر عن 17 و (3) يمكن أن تسفر عن 13 و (4) يمكن أن تسفر عن 10 و (5) يمكن أن تسفر عن 16فا (6) يمكن أن تسفر عن 15 و (7) يمكن أن تسفر عن 11 واط (8) يمكن أن تسفر عن 12

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

هذه أسئلة الإجابات تبدو قريبة من ما أريد، لكنني لست متأكدا مما إذا كانت الإجابات تسمح لي بتقييد الإخراج إلى تسلسل محدد في وقت مبكر.

---

يحرر:

لتوضيح أكثر قليلا لا أريد تخزين التسلسل الأصلي، أو التسلسل الخلفي. أريد أن أنظر وظيفة F () من التسلسل الأصلي.

ما هو الإحباط هو أنني رأيت هذا، لا أستطيع أن أتذكر ما يكفي عن ذلك للعثور عليه مرة أخرى مع Google.

خوارزمية فيشر ييتس كبيرة لتصدر أو خلط سطح السفينة، لكنها ليست ما أبحث عنه.

Answer 1

هناك وظيفة بسيطة تنشئ التقبيل [0..m-1] لاجل منحه m. وبعد فقط اختيار عدد k, ، رئيسا نسبيا ل m واسمحوا f(i)=(k*i) mod m. وبعد هذا يولد دائما التقليب (لا يكرر 0<=i<m). انها تعمل بشكل أفضل إذا k أكبر من m.

على سبيل المثال، م = 20، دع k = 137 (رمز بيثون، % يعني modulo):

 >>> [(137*i) % 20 for i in range(20)]
 [0, 17, 14, 11, 8, 5, 2, 19, 16, 13, 10, 7, 4, 1, 18, 15, 12, 9, 6, 3]

هذا بسيطة للغاية PRNG، لا ضمانات حول خصائصها الإحصائية.

Answer 2

هذا السؤال هو مماثل لإحباط بطاقات سطح السفينة (M + 1)، مرقمة [N، ...، N + M]. لاحظ أن الترقيم (وبالتالي n) غير مهم؛ ما يهم هو أننا نستطيع أن نخبر البطاقات. (يمكنك ببساطة إضافة n في وقت لاحق إذا رغبت في ذلك.)

للقيام بما تريد، يمكنك إجراء فيشر ييتس خلط ورق اللعب و فقط تتبع المؤشرات التي تم اختيارها للخلاف حتى الآن. سيسمح لك ذلك بتجنب تخزين نسخة أخرى من القيم نفسها، على النحو المطلوب.

Answer 3

سؤالك مربكا بعض الشيء، حيث يبدو أنك تريد الحصول على جميع التسلسل الأصلي مرة أخرى، ولكن بعد ذلك لديك كل من 4 و 8 رسم خرائط إلى 10، ولا شيء رسم الخرائط إلى 12.

إذا كنت تعني بالفعل تعيين 1: 1، فما الذي تبحث عنه هو التقليب العشوائي للمجموعة الأصلية. هناك طرق للقيام بذلك مع أو بدون جمع المجموعة الأولى (ولكن ستحتاج إلى شيء ينشئه، أو تتبع أين أنت).

أيضا، لاحظ أن N غير مهم. يمكنك دائما استخدام 0،1،2، ... M ثم أضف N إلى كل شيء إذا لزم الأمر.

على افتراض أنني قمت بتفسير هذا بشكل صحيح وأنت تبحث بالفعل عن خوارزمية خلط ورق اللعب (أي اعتبارات عشوائية، تسمى النفايات عن طريق القياس لإخلاء سطح السفينة)، ألق نظرة على فيشر ييتس

تحرير] موافق، بناء على التحديث الخاص بك، المشكلة التي تواجهها هي هذا: لا تريد أن ترميز البداية بشكل صريح، ولكن يجب أن تشفيرها بطريقة أو بأخرى من أجل بناء f. أسهل طريقة هي فقط تخزين المؤشرات المسموح بها بالفعل في صفيف، ولكن إذا كنت لا ترغب في القيام بذلك لسبب ما (مثل كبير جدا)، فيمكنك أن ترفعها بطرق مختلفة. لا يوجد غداء مجاني على الرغم من وجود حدود نظرية المعلومات حول طريقة بسيطة هذا. على أي حال، يمكنك الحصول على بعض الأفكار من البحث عن العمل على "برسام الترميز" على سبيل المثال شيء مثل هذه الورقة

Answer 4

هنا بعض pseudocode في لغتي المكياج الخاصة بي:

function f(array a)
    array newArray
    while a.size() == 0
        int position = randomNumber(1 to a.size())
        int removedNumber = a[position]
        a.remove(position)
        newArray.insertAtEnd(removedNumber)
    end while
    return newArray

Answer 5

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

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

Answer 6

إذا كنت ترغب في رسم الخرائط 1: 1، فانتقل مع فيشر - ييتس كما هو مذكور في الإجابات الأخرى.

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

على سبيل المثال، في C ++، يمكنك استخدام RAND () بالطريقة التالية -

result = rand() % (m+1) + n

لذلك على سبيل المثال الخاص بك،

result = rand() % 8 + 10

سوف تنتج عدد صحيح بين 10 و 17.

Answer 7

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

Answer 8

يمكنك توليد التقليب من الأعداد الصحيحة الأولى من خلال استخدام Cipher Cipher و XOR للطي، حسب إجابتي السابقة.

Answer 9

ليس من الممكن إرجاع القيم دون تخزين نتائج الوظيفة الأصلية في مكان ما. منطق:

يخبرك مولد الأرقام العشوائية بإعادة هذه القيم من التسلسل الأصلي: 5، 11th، 3rd.

لذلك تخطي القيم الأربعة الأولى، وإرجاع 5، تخطي 5 آخر، وإرجاع 11th ... الآن كيف يمكنك العودة الثالثة دون حفظ ذلك في مكان ما؟

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

انهيت قضيتي.

Answer 10

وصف المدخلات الخاصة بك f(x) => x + 9, ، أو أكثر عموما f(x) => n - 1 + x كما x يبدأ في 1.

أنت تصل إلى سؤال آخر التي تصف وظيفة r(x) التي خرائط x إلى قيمة خلط، 0 <= r(x) <= m.

وبالتالي f(r(x) + 1) أو (r(x) + n)يجب أن تعطيك القيمة التي تريدها.

لصغيرة m, ، يجب أن تكون أيضا قادرا على العثور على بذور مولد رقم عشوائي قياسي بواسطة Trail والخطأ الذي يولد بعد ذلك m+1 القيم المميزة عند اتخاذ وزارة الدفاع m+1 إذا كنت لا تريد رمز المولد الخاص بك.