過濾A010784序列的最快方法

Question

OEIS上的A010784序列是僅包含具有不同數字的數字的序列。這是一個有限的數量。

我一直在試圖做的是找到幾個數字在這個序列中的某些屬性。
例如：圖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

什麼我目前正在做的是從最高可能的不同數量，這是和最高的唯一編號量級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 =
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的練習留下了細節。

較長的解釋：

假設有計算用於在10個鹼基所代表的數number_str大小的過程

magnitude(number_str) 

，因此該過程返回0，如果number_str含有至少一個雙如果number_str每個數字都不同，但是將數字乘以2會導致數字出現多次，那麼將出現1個數字。

此過程c一個可以在另一個

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("") 

這是一個只需不到一秒的運行;這找到了答案'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，你做10cM。

例如，在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)) 

Answer 4

可以削減一些樹枝，如果你只是在尋找最高的數字。從6 x 11 = 66你也知道11的幅度至多是5.一旦你知道一個幅度大於等於5的較高數字，你可以跳過11. 11.