أعطاك زميل الرقم 13 وطلب ترتيب أربع بطاقات. لا يكفي الرقم وحده؛ تحتاج أسماء البطاقات وترتيب المقارنة ونقطة بدء الترقيم. سنثبت هذه الشروط، ثم نجد الصف المقصود بالحساب، ونعيده إلى رقمه للتأكد من أن الرسالة لم تفقد معناها.
الخلاصة السريعة
- البطاقات متميزة، وترتيب المقارنة A < B < C < D.
- لدينا 24 ترتيبًا، برتب تبدأ من صفر وتنتهي عند 23.
- الصف CADB رتبته 13؛ أي إنه الرابع عشر عند العد من واحد.
- نستعيده بالقسمة والباقي على أحجام المجموعات 6 ثم 2 ثم 1 ثم 1.
- الرقم نفسه لا يحتفظ بمعناه إذا غيرنا ترتيب أسماء البطاقات.
اكتب اتفاق القائمة قبل استعمال الرتبة
نقرأ صف البطاقات من اليسار إلى اليمين. عند مقارنة صفين، ننظر إلى أول موضع مختلف؛ يسبق الصف الذي يحمل فيه الحرف الأسبق باتفاقنا. لهذا يسبق ABDC الصف ACBD، لأن موضع الاختلاف الأول يحمل B في الأول و C في الثاني. لا نبدأ المقارنة بآخر حرف.
تعرض وثائق SageMath رتبة التبديل ضمن الترتيب المعجمي، وترميز Lehmer الذي يعد العناصر الأصغر إلى يمين كل عنصر. [1] سنطبق الفكرة على بطاقاتنا، مع ترقيم يبدأ من الصفر.
عبارة «أربع بطاقات» هنا تعني ظهور A و B و C و D مرة واحدة لكل منها. لا نسمح بالحذف أو بتكرار حرف. وبعد اختيار البطاقة الأولى تبقى ثلاثة خيارات للثانية، ثم اثنان للثالثة، ثم اختيار واحد للأخيرة؛ حاصل 4 × 3 × 2 × 1 = 24.
لا نعطي البطاقات قيمًا مالية أو درجات جودة. الرتبة عنوان داخل قائمة مرتبة، ولا تجعل الصف ذا الرقم الأكبر أفضل. وهي ليست عدد النقلات اللازمة لتحريك بطاقات من صف البداية إلى صف آخر؛ لم نحدد في المسألة حركة مسموحة أصلًا.
قسّم الأربعة والعشرين إلى مجموعات واضحة
إذا ثبتنا A في البداية، أمكن ملء الباقي بست طرق: ثلاث اختيارات، ثم اثنتان، ثم واحدة. الأمر نفسه إذا بدأنا B أو C أو D. لذلك تشغل مجموعة A الرتب من 0 إلى 5، ومجموعة B من 6 إلى 11، ومجموعة C من 12 إلى 17، ومجموعة D من 18 إلى 23.
لنكتب مجموعة C كاملة حتى نراجع ترتيبها: CABD, CADB, CBAD, CBDA, CDAB, CDBA. أول صفين يبدآن CA، ثم صفان يبدآن CB، ثم صفان يبدآن CD. داخل كل زوج تتبقى بطاقتان، فنقدم ترتيبهما الموافق لاتفاق المقارنة.
يمكنك الآن إيجاد CADB دون إنشاء بقية القائمة. مجموعتا A و B تسبقان بدايته، وفيهما اثنا عشر صفًا. داخل مجموعة C يسبقه CABD وحده. إذن عدد الصفوف السابقة 13، وهذا هو الرقم الذي نسميه الرتبة الصفرية.
احسب من اليسار مع حذف كل اختيار
ابدأ بالقائمة المتاحة A ثم B ثم C ثم D. عند C توجد بطاقتان أصغر لم نستخدمهما: A و B. كل واحدة تستطيع بدء ستة صفوف، فنضيف 2 × 6 = 12. احذف C؛ لا يصح إبقاؤه في قائمة الخيارات للموضع التالي.
المتاح الآن A و B و D. نريد A، ولا يسبقه خيار، فنضيف صفرًا مضروبًا في 2. بعد حذفه يتبقى B و D. نريد D، ويسبقه B، فنضيف 1 × 1 = 1. وأخيرًا B وحده، فتكون الإضافة صفرًا.
| المختار | الأصغر المتاح | حجم المجموعة | الإضافة |
|---|---|---|---|
| C | 2 | 6 | 12 |
| A | 0 | 2 | 0 |
| D | 1 | 1 | 1 |
| B | 0 | 1 | 0 |
قائمة العد هي 2, 0, 1, 0، والمجموع 12 + 0 + 1 + 0 = 13. لا تقرأ 2010 عددًا عشريًا جديدًا؛ لكل موضع وزن مختلف في الجدول. كما لا تستبدل الأوزان كلها بالستة لمجرد أن أول مجموعة احتوت ستة صفوف.
عد من الرقم إلى البطاقات
نبدأ بالرقم 13 والقائمة الكاملة. قسمة 13 على 6 تعطي خارجًا صحيحًا 2 وباقيًا 1. اختر العنصر عند الفهرس 2 من القائمة: C، لأن فهرس A صفر، و B واحد. الباقي 1 يحدد موضعنا داخل مجموعة C بعد تجاوز مجموعتين كاملتين.
احذف C، واقسم الباقي 1 على 2. الخارج صفر، فنأخذ A من بداية القائمة الجديدة، ويبقى 1. احذف A، ثم اقسم 1 على 1؛ الخارج واحد، فنأخذ D من القائمة B و D، ويصير الباقي صفرًا. البطاقة الأخيرة B، فيكتمل CADB.
الوزن الأخير واحد لأن ترتيب قائمة فارغة بعد اختيار البطاقة الأخيرة له طريقة واحدة: ألا نضع شيئًا إضافيًا. لم نصل إلى قسمة على صفر. وهذه الخطوة تسجل الباقي الأخير دون اختراع بطاقة خامسة.
ثلاثة أخطاء تغير معنى الرقم
أولها خلط بدء الترقيم. «الصف الرابع عشر» يقابل الرتبة 13 عندنا. إذا أرسلت 14 إلى خطواتنا فسوف تحصل على CBAD. كلا الصفين صالح، لكنهما مختلفان؛ فحص وجود الحروف الأربعة وحده لا يكشف هذا الخطأ.
ثانيها تغيير اتفاق المقارنة إلى A < C < B < D. عندئذ تسبق C مجموعة واحدة فقط، ويصبح رقم CADB هو 7: ستة صفوف تسبق C وصف واحد إضافي داخلها. احفظ ترتيب الرموز مع الرقم، ولا تفترض أن أي ترتيب للقائمة المتاحة سيعيد الجواب نفسه.
ثالثها إدخال A مرتين بدل أربع هويات مختلفة. أعداد المجموعات السابقة بُنيت على التمييز الكامل. نرفض في برنامج التمرين قائمة الرموز المكررة، وكذلك صفًا ينقصه حرف أو يحتوي حرفًا غريبًا، بدل إعطاء رقم يبدو معقولًا لمجال آخر.
افحص الرجوع والقائمة المستقلة
تنتج itertools.permutations تبديلات وفق ترتيب المدخل؛ ومع مدخل مرتب تكون النتائج مرتبة معجميًا. وتميز العناصر بحسب مواضعها. [2] استخدمناها مرجع تعداد مستقلًا لبطاقات متميزة.
ولّدنا القوائم الكاملة للأطوال من صفر إلى سبعة، ثم قارنا رقم كل صف بمكانه في التعداد، وأعدنا الصف من الرقم. مجموع الصفوف المفحوصة 5914. لم نكتف بأن تلغي دالتانا بعضهما؛ قد تتفق دالتان مخطئتان على ترتيب مختلف، ولذلك قارناهما بالقائمة الثالثة.
وعند أربع بطاقات، أعادت الرتبة صفر ABCD، والرتبة 23 أعادت DCBA. رفضت دالتنا الرتبتين سالب واحد و 24، لأنها لا تقع في المجال المحدد. هذا اتفاق برنامجنا، ولا نزعم أن كل مكتبة تتعامل بالطريقة نفسها مع المدخل الخارج عن المجال.
احتفظ في سجل صغير بأسماء الرموز مرتبة، وبداية الترقيم، والرقم المطلوب، والصف المستعاد. إذا اختلفت النتيجة فراجع هذه الخانات قبل تغيير الحساب. الفحص المذكور تنفيذ برمجي على أمثلة محددة؛ لم نقس زمن الأداء أو نختبر بيانات كبيرة.