过滤A010784序列的最快方法

Question

OEIS上的A010784序列是只包含有不同数字的数字的序列。这是一个有限的数量。

我一直想做的是在这个序列中找到几个具有特定属性的数字。

例句:6是10级的一个明显数字，具体如下：

• 6x1=6
• 6x2=12
• 6x3= 18
• 6 x4=24
• 6x5=30H 210<
• >H 1116x6=36H 212H 1136x7=42H 214H 1156x8=48H 216H 117>6x9H 218>6x 10 <>60<>编码H 220/码><>6<><>6<>6<>6码<6 2 2 2码<
• <6 2 2 2码<6 2 2 2码<6 2 2 2码<6 2 2 2码<6 2 2 2码<6 2 2 8<6 2 2 2码><6 6 2 0><6 6 2码><6 6 2 2码><6 6 2码><6 6 2 2码><2 6 2 2 2码<6 2 2 0><6 6 2 0 2码><6 6 2 8<6 6 2 8<6 6 2 8<6 6 2 0<6 6 2 6(？)

现在我正在尝试几个数量级可以得到的最高数字。

假设所有订单从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，那么对于任何乘法和2.N，在结果的前k位内，数字都会出现两次，那么任何数字b1...bm a1...ak也不会出现。这提供了一个绝对更快的递归枚举过程，因为它减少了大量的搜索空间。剩下的细节作为一项操作。

较长的解释：

假设有一个程序

 magnitude(number_str)

这将计算以10基表示的数字number_str的大小，以便如果number_str至少包含一个数字的两次出现，则该过程返回0，如果number_str的每一个数字都是不同的，但将该数字乘以两次，则返回0，以此类推。

这个过程可以在另一个过程中实现。

 unique_digits(number_str)

如果number_str中的所有数字都是唯一的，则返回true，否则为false。

现在可以将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) <=震级(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("")

这里有一个不超过1秒的运行，它找到了答案'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

这难道不是一个排列问题吗？对于给定的震级M，你做10厘米。

例如，大小为2的从0..9中选择2位的方法有多少种？(实际上，它应该是1..9和0.9之间的一位数，其中第二位数与第一位数不匹配。)

你当然不需要把它们全部浏览一遍，然后检查它们。只需设置一个集合并选择一个，然后选择另一个。更好的是，从零开始创建它们。首先做一切从1开始的事情(10，12，13，14，等等)，然后一切从2开始，等等。

Answer 3

你有两个问题：

1)迭代A010784序列。

使用itertools.permutations生成连续可能的数字。

( 2)计算一个数的大小。

您可以确定一个数字是否只有此代码段的唯一数字：

def unique_num(x):
    return len(str(x)) == len(set(str(x))