أوجد التباديل حيث لا يبقى أي عنصر في مكانه

Question

أنا أعمل مع التباديل حيث يختلف كل عنصر عن موقعه الأصلي.أرغب في الحصول على خوارزمية تعطيني {طول الإدخال والصف والرقم} رقم الإخراج.هنا مثال:

إذا كان طول الإدخال أربعة، فإن جميع التباديل للرقم 0123 هي:

0123,0132,0213,0231,0312,0321,
1023,1032,1203,1230,1302,1320,
2013,2031,2103,2130,2301,2310,
3012,3021,3102,3120,3201,3210

التباديل التي لا يوجد فيها رقم في نفس المكان (كل رقم يتحرك):

1032,1230,1302,
2031,2301,2310,
3012,3201,3210

يبدأ الترقيم عند 0، لذا إذا كان إدخال الدالة هو {4,0,0}، فيجب أن يكون الإخراج هو الرقم 0 (أقصى اليسار) من التقليب 0 (الأول).الرقم الأول من 1032 هو 1

إذا كان الإدخال {4,1,1} فإن الإخراج هو الرقم الثاني من 1230، وهو 2.

قد يكون رقم الصف أكبر من عدد التباديل.في هذه الحالة، خذ الباقي من معامل التباديل (في الحالة المذكورة أعلاه، معامل الصف 9).

في لغة C سيكون رائعا.

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

Answer 1

ونهج القوة الغاشمة في بيثون (يمكنك استخدام لاختبار تنفيذ C الخاص بك):

#!/usr/bin/env python
from itertools import ifilter, islice, permutations

def f(length, row, digit):
    """
    >>> f(4, 0, 0)
    1
    >>> f(4, 1, 1)
    2
    """
    # 1. enumerate all permutations of range (range(3) -> [0,1,2], ..)
    # 2. filter out permutations that have digits inplace
    # 3. get n-th permutation (n -> row)
    # 4. get n-th digit of the permutation (n -> digit)
    return nth(ifilter(not_inplace, permutations(range(length))), row)[digit]

def not_inplace(indexes):
    """Return True if all indexes are not on their places.

    """
    return all(i != d for i, d in enumerate(indexes))

def nth(iterable, n, default=None):
    """Return the nth item or a default value.

    http://docs.python.org/library/itertools.html#recipes
    """
    return next(islice(iterable, n, None), default)

if __name__=="__main__":
    import doctest; doctest.testmod()

Answer 2

لماذا لا نبني شجرة ونكررها؟

على سبيل المثال، إذا كان لديك الأرقام 0123, ، فأنت تعلم أن الرقم الموجود في أقصى اليسار يمكن أن يكون فقط من set {1,2,3}.سيكون هذا بمثابة المستوى الأول في شجرتك.

وبعد ذلك، إذا سلكت المسار الذي يبدأ بالرقم 1، فلديك ثلاثة خيارات فقط، {0, 2, 3}.إذا سلكت المسار الذي يبدأ بالرقم 2 في المستوى الأول، فلديك خياران فقط {0,3} (نظرًا لأنه لا يمكنك استخدام 1 في الرقم الثاني من اليسار وكان الرقم 2 مستخدمًا بالفعل (يمكنك إخراج الرقم 2 من قائمة اختياراتك))، وما إلى ذلك.

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

ل n > 10 يمكن أن يصبح توليد جميع التباديل ومن ثم التصفية مشكلة.أعتقد أن بناء الشجرة من شأنه أن يقلل هذا بشكل كبير.

يمكنك بناء الشجرة بسرعة إذا لزم الأمر.يمكن تحديد طلبك من خلال كيفية اجتياز الشجرة.