أسرع طريقة لتصفية تسلسل A010784

Question

التسلسل A010784 في OEIS هو التسلسل الذي يحتوي فقط على أرقام ذات أرقام مميزة.وهذا مبلغ محدود.

ما كنت أحاول القيام به هو العثور على عدة أرقام في هذا التسلسل بسمات معينة.
على سبيل المثال:6 هو رقم مميز بقيمة 10.ويمكن العثور على هذا على النحو التالي:

• 6 × 1 = 6
• 6 × 2 = 12
• 6 × 3 = 18
• 6 × 4 = 24
• 6 × 5 = 30
• 6 × 6 = 36
• 6 × 7 = 42
• 6 × 8 = 48
• 6 × 9 = 54
• 6 × 10 = 60
• 6 × 11 = 66 (ستتان؛هذان ليسا رقمين مختلفين.)

الآن أحاول الحصول على أعلى الأرقام المتاحة لعدة مقادير من النظام.
لنفترض أن جميع الطلبات من 1 إلى 20.

ما أفعله حاليًا هو تنفيذ حلقة من أعلى رقم مميز ممكن، وهو 9,876,543,210 وأعلى رقم فريد بحجم 1، وصولاً إلى رقم منخفض جدًا.
تشعر هذه الطريقة لأقصى حد غير فعال.على الأقل بالنسبة لي.

أنا متأكد تمامًا من أنني أفتقد بعض الأشياء المتعلقة بالتخصيم والتي من المفترض أن تجعل الأمور أسرع كثيرًا.

def unique_num(num):
    # Check whether number is unique.
    return Boolean

def unique_num_magnitude(num):
    # Check of which magnitude the unique number is
    return Integer

# Dictionary with the current highest values
# for each magnitude.
values = {1: 987654321...}

# Set limits
upper_limit = 9876543210
lower_limit = 1

for numbers in range(upper_limit, lower_limit, -1):
    unique = unique_num(num) # Boolean
    if (unique):
        magnitude = unique_num_magnitude(num)
        if (values[magnitude] < num):
            values[magnitude] = num

Answer 1

بالتأكيد هناك طريقة أفضل.يجب عليك بناء الأرقام من الأسفل إلى الأعلى، أي.إذا كان الرقم a1...ak (هذه أرقام k) ليس بحجم N بحيث يظهر الرقم مرتين ضمن أول أرقام k من النتيجة لأي مضاعف 2..N، فلا يكون أي رقم b1...bm a1...ak.يوفر هذا إجراء تعداد عودي أسرع بشكل قاطع لأنه يقلل من مساحة البحث بشكل كبير.التفاصيل المتبقية كتمرين على OP.

شرح أطول:

لنفترض أن هناك إجراء

 magnitude(number_str)

الذي يحسب حجم الرقم number_str ممثلة بقاعدة 10، بحيث يُرجع الإجراء 0 if number_str يحتوي على تكرار مزدوج واحد على الأقل للرقم، 1 if number_str يحتوي على كل رقم مميز ولكن ضرب الرقم في اثنين يؤدي إلى ظهور رقم عدة مرات، وما إلى ذلك.

يمكن تنفيذ هذا الإجراء من حيث إجراء آخر

 unique_digits(number_str)

والذي يعود صحيحًا إذا كانت جميع الأرقام موجودة number_str فريدة من نوعها، وإلا فهي كاذبة.

والان اذن magnitude يمكن تنفيذها كما

 magnitude(number_str):
   n = str_to_int(number_str)
   k = n
   i = 0
   while (unique_digits(int_to_str(k))):
     k = k + n
     i = i + 1
   return i

الآن هذا magnitude يمكن تغيير الإجراء إلى أ nocarry_magnitude الذي يغير الشيك بمهارة:

 nocarry_magnitude(number_str, limit):
   l = length(number_str)
   assert (l > 0)
   n = str_to_int(number_str)
   k = n
   i = 0
   while (unique_digits(right_substring(int_to_str(k), l))):
     k = k + n
     i = i + 1
     if (i == limit):
       break
   return i

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

 magnitude(s) <= nocarry_magnitude(s, M) for large M

مثلا خذ رقم 19:

 19 * 1 = 19
 19 * 2 = 38
 19 * 3 = 57
 19 * 4 = 76
 19 * 5 = 95
 19 * 6 = 114 // magnitude("19") = 5
 19 * 7 = 133 // nocarry_magnitude("19", 100) = 6

ما كتبته أعلاه في الوصف القصير هو أنه إذا

 nocarry_magnitude(s, x) == k     for x > k

ثم لأي سلسلة تم الحصول عليها عن طريق التثبيت اللاحق s (أشير إلى ذلك ب x + s أدناه)، فإنه يحمل ذلك

 x : string of digits
 magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
 when m >= magnitude(x + s)

التفاوت الأول يأتي من الادعاء أعلاه والثاني واضح من تعريف nocarry_magnitude.لاحظ أن الحجم (x + s) <= الحجم (المقاسات) هو غير نظرية بشكل عام كما يتضح من

 magnitude( "56")  = 1  // 56 * 2 = 112
 magnitude("256")  = 12 // the first duplicate occurs at 3328

الذي يسببه الحمل. nocarry_magnitude يتجاهل الحمل وهذا هو السبب في أن لاحقة السلسلة دائمًا ما تكون ذات حجم كبير مثل أي امتداد لها (باتجاه اليسار، أيأرقام ذات ترتيب أعلى).

يمكنك الآن كتابة إجراء عودي أسرع بشكل ملحوظ مثل هذا للبحث عن أرقام بحجم M على الأقل:

 search(str):
   if (str != ""):
     int n = nocarry_magnitude(str, M)
     if (n < M):
       return      # the optimization
     int k = magnitude(str)
     if (k >= M):
       store_answer(str)
   for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
             '10', '20', '30', '40', '50', '60', '70', '80', '90']:
     search(d + str)

 search("")

إليك تطبيق Python الكامل (البحث عن الحجم 36):

def unique_digits(s):
    r = (len(list(s)) == len(set(s)))
    return r

def magnitude(s):
    n = int(s)
    k = n
    assert n > 0
    i = 0
    while (unique_digits(str(k))):
        k = k + n
        i = i + 1
    return i

def nocarry_magnitude(s, limit):
    l = len(s)
    assert l > 0
    n = int(s)
    assert n > 0
    k = n
    i = 0
    while (unique_digits(str(k)[-l:])):
        k = k + n
        i = i + 1
        if (i >= limit):
            break
    return i

M = 36

def search(s):
    if (not(s == "")):
        n = nocarry_magnitude(s, M)
        if (n < M):
            return
        k = magnitude(s)
        if (k >= M):
            print "Answer: %s |" % s,
            i = int(s)
            k = i
            n = 1
            while (n <= M):
                print k,
                k = k + i
                n = n + 1
            print
    for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
              '10', '20', '30', '40', '50', '60', '70', '80', '90']:
        search(d + s)

search("")

وهنا جولة تستغرق أقل من ثانية واحدة؛يؤدي هذا إلى العثور على الإجابة "27" والتي يبدو أنها الرقم الفريد الذي يوفر الحجم القياسي 36:

Answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405
             432 459 486 513 540 567 594 621 648 675 702 729 756 783
             810 837 864 891 918 945 972

Answer 2

أليست هذه مجرد مشكلة تبديل؟للحصول على حجم معين من الكود العام ، هل تفعل 10 سم.

على سبيل المثال ، بحجم 2 ، كم عدد الطرق المتاحة لاختيار رقمين من 0..9؟(في الواقع ، يجب أن يكون واحدًا من 1..9 وواحد من 0..9 حيث لا يتطابق الرقم الثاني مع الأول.)

أنت بالتأكيد لست بحاجة إلى المرور بها جميعًا والتحقق منها.ما عليك سوى إعداد مجموعة واختيار واحدة ، ثم اختيار مجموعة أخرى.الأفضل من ذلك ، فقط قم بإنشائها من الصفر.أولاً ، افعل كل شيء يبدأ بـ 1 (10 ، 12 ، 13 ، 14 ، إلخ) ثم كل شيء يبدأ بـ 2 ، إلخ.

Answer 3

لديك مشكلتان:

1) التكرار على تسلسل A010784.

استخدم itertools.permutations لإنشاء أرقام متتالية محتملة.

2) حساب مقدار الرقم.

يمكنك تحديد ما إذا كان الرقم يحتوي على أرقام فريدة فقط مع مقتطف الرمز هذا: Genacodicetagpre

Answer 4

يمكنك قطع بعض الفروع إذا كنت تبحث فقط عن أكبر عدد.من خلال رمز الترميز العام ، تعلم أيضًا أن الحجم 11 هو 5 على الأكثر. بمجرد أن تعرف رقمًا أكبر بحجم>= 5 ، يمكنك تخطي 11.