العثور على مجموعة من التباديل، مع وجود قيود

Question

لدي مجموعة من أرقام N ^ 2 و BINS N. من المفترض أن يكون لكل صندوق أرقام n من المجموعة المعينة إليه. المشكلة التي أواجهها هي العثور على مجموعة من التوزيعات التي تعريش الأرقام إلى الصناديق، مرضية القيد، أن كل زوج من الأرقام يمكن أن يشارك نفس الحاوية مرة واحدة فقط.

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

مثال مجموعة من 3 التباديل تلبي قيد القيد ل n = 8:

 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

 0  8 16 24 32 40 48 56
 1  9 17 25 33 41 49 57
 2 10 18 26 34 42 50 58
 3 11 19 27 35 43 51 59
 4 12 20 28 36 44 52 60
 5 13 21 29 37 45 53 61
 6 14 22 30 38 46 54 62
 7 15 23 31 39 47 55 63

 0  9 18 27 36 45 54 63
 1 10 19 28 37 46 55 56
 2 11 20 29 38 47 48 57
 3 12 21 30 39 40 49 58
 4 13 22 31 32 41 50 59
 5 14 23 24 33 42 51 60
 6 15 16 25 34 43 52 61
 7  8 17 26 35 44 53 62

التقليب الذي لا ينتمي إلى المجموعة أعلاه:

 0 10 20 30 32 42 52 62
 1 11 21 31 33 43 53 63
 2 12 22 24 34 44 54 56
 3 13 23 25 35 45 55 57
 4 14 16 26 36 46 48 58
 5 15 17 27 37 47 49 59
 6  8 18 28 38 40 50 60
 7  9 19 29 39 41 51 61

بسبب تصادمات متعددة مع التقليب الثاني، حيث، على سبيل المثال، كلاهما يقلقون الأرقام 0 و 32 في صف واحد.

---

يعد تعداد ثلاثة سهلة، وهو يتألف من 1 التقليب التعسفي ونقله ومصفوفة حيث تصنع الصفوف من قطريات مصفوفة السابقة.

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

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

---

تعديل:

إليك بعض الكود لدي.الشفرة

إنه جشع، وعادة ما ينتهي بعد العثور على التقليب الثالث. ولكن يجب أن يكون هناك مجموعة من التباديلات N على الأقل تلبية المشكلة.

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

Answer 1

ما تريده هو تصميم كتلة الحركة. وبعد باستخدام التسمية على الصفحة المرتبطة، تريد تصميمات الحجم (N ^ 2، N، 1) للحصول على أقصى حد K. سيعطيك هذا التبادلات N (N + 1)، باستخدام تسمياتك. هذا هو الحد الأقصى الممكن من الناحية النظرية من الناحية النظرية من خلال حجة العد (انظر التفسير في مقال اشتقاق B من V و K و Lambda). هذه التصميمات موجودة ل n = p ^ k لبعض prime p و hemteger k، باستخدام طائرة أفيشية. يتم تخمين أن الطائرات الفائضة الوحيدة الموجودة من هذا الحجم. لذلك، إذا تمكنت من تحديد N، فربما تكفي هذه الإجابة.

ومع ذلك، إذا بدلا من الحد الأقصى لعدد التبولات من الناحية النظرية، فأنت تريد فقط العثور على عدد كبير (أكثر ما تستطيع من أجل n ^ 2)، لست متأكدا من ما يسمى دراسة هذه الكائنات.

Answer 2

اصنع صفيف 64 × 64 × 8: Bool ممنوع [i] [J] [ك] مما يدل على ما إذا كان الزوج (I، J) ظهر في الصف K. في كل مرة تستخدم فيها الزوج (I، J) في الصف K، ستقوم بتعيين القيمة المرتبطة في هذه الصفيف إلى واحد. لاحظ أنك ستستخدم فقط نصف هذه الصفيف التي <j.

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

ربما تكون هناك تحسينات يجب أن تكون قادرا على التوصل إلى ذلك أثناء تنفيذه، ولكن هذا يجب أن يفعل ذلك جيدا.

Answer 3

ربما يمكنك إعادة صياغة مشكلتك في نظرية الرسم البياني. على سبيل المثال، تبدأ مع الرسم البياني الكامل مع قمة N × n. في كل خطوة، تقوم بتقسيم الرسم البياني إلى n n-cliques، ثم قم بإزالة جميع الحواف المستخدمة.

لهذا الحال N = 8، يحتوي K64 على 64 × 63/2 = 2016 حواف، وأربعة وستون الكثير من K8 تحتوي على 1792 حواف، لذلك مشكلتك مايو لا يكون مستحيلا :-)

Answer 4

الحق، والنمط الجشع لا يعمل لأنك نفدت الأرقام.

من السهل أن نرى أنه لا يمكن أن يكون هناك أكثر من 63 حالة من التباديل قبل أن تنتهك القيد. في 64، سيتعين عليك إقران واحدة على الأقل من الأرقام مع آخر تم إقرانها بالفعل. مبدأ الحمام.

في الواقع، إذا كنت تستخدم جدول الأزواج المحظورة، اقترحت سابقا، فجد أن هناك كحد أقصى فقط N + 1 = 9 التباديل ممكن قبل نفاد. يحتوي الجدول على N ^ 2 × (n ^ 2-1) / 2 = 2016 قيود غير زائدة عن الحاجة، وسيقوم كل التقليب الجديد بإنشاء N X (N اختر 2) = 28 زوجا جديدا. لذلك سيتم استخدام جميع الاقتران بعد 2016/28 = 9 التباديل. يبدو أن هذا الأمر يحقق أن هناك بعض التبادلات قليلة هي المفتاح لحل المشكلة.

يمكنك إنشاء قائمة بتصباتات N مرقمة N = 0 ... N-1 كما

A_ij = (i * N + j + j * n * N) mod N^2

والتي تولد مبناه جديد من خلال تحويل الأعمدة في كل التقليب. الصف العلوي من التقليب NTH هي قطرات التقليب N-1. تحرير: عفوا ... هذا يبدو فقط للعمل عندما يكون n رئيس الوزراء.

هذا يخطئ التقليب الأخير، والذي يمكنك الحصول عليه عن طريق نقل المصفوفة:

A_ij = j * N + i