用於追蹤可刪除素數的遞歸函數 - Python 3

Question

可刪除素數是一個素數，可以按特定順序刪除其數字以始終創建素數，並最終以一位數素數結束。例如，3301是一個可刪除的素數，因爲它可以像這樣操作：3301 -> 331 -> 31 -> 3。我試圖在Python中編寫一個遞歸函數，將可刪除的素數的所有路徑追溯到其單個數字根，但我完全被卡住了。它已經超出了我的頭，我甚至無法遵循我自己的代碼。該函數的期望輸出的一個完整的例子是沿getTraces(3793)回報[[3793, 373, 73, 7], [3793, 373, 73, 3], [3793, 373, 37, 7], [3793, 373, 37, 3], [3793, 379, 79, 7], [3793, 379, 79, 3], [3793, 379, 37, 7], [3793, 379, 37, 3]]

線的東西這裏是我有功能的當前版本（如果有任何幫助）。我試圖讓它返回所有可能的路徑到單個數字素數的列表，但是我無法將自己的頭圍繞遞歸思考，讓它跟蹤所有路徑並將它們整齊地放在列表中：

def getTraces(prime): 
    paths = [] 
    print("Parents: " + str(asc(prime))) 
    for p in asc(prime): 
     if len(str(p)) == 1: 
      print("One Digit Prime: "+ str(p)) 
      return [p] 
     else: 
      traceArray = getTraces(p) 
      print("Trace: " + str(traceArray)) 
      if traceArray != []: 
       for t in traceArray: 
        paths.append(str(prime) + ", " + str(p) + ", " + str(t)) 
       #traceString = str(p) + ", " + str(traceArray) 
    return paths 

此功能只返回一個主要的所有的家長名單（全部除去了一個數字可能的素數），並在getTraces（）函數

def asc(prime): 
    adj = [] 
    if(isPrime(prime)): 
     s = str(prime) 
     if len(s) == 1: return [] 
     for i in range(0, len(s)): 
      num = int(s[:i] + s[i+1:]) 
      if isPrime(num): 
       if not num in adj: 
        adj.append(num) 
    else: 
     print("That is not a prime number!") 
     return None 
    return adj 

和一個非常好的工具使用我檢查數字是否爲素數的方法：

def isPrime(x): 
    if x <= 1: return False 
    for i in range(1, int(sqrt(x)) + 1): 
     if not gcd(i, x) == 1: 
      #print(i) 
      return False 
    return True 

Answer 1

我終於能夠解決我的問題，所以我想我也可以發表我的回答，因爲我無法刪除的問題。我最終放棄了試圖遞歸地做這件事，因爲我想出了一種不用遞歸的方法，但是我很欣賞每個人提供的幫助和指針。這裏是我的解決方案：

def trace(prime): 
    def sub(paths): 
     result = [] 
     """Increases path depth by one""" 
     for path in paths: 
      pathResult = [] 
      for parentOfLast in asc(path[len(path)-1]): 
       pathResult.append(path + [parentOfLast]) 
      #print("Path: " + str(pathResult)) 
      result += (pathResult) 
     return result 
    result = [[prime]] 
    while len(result[0]) < len(str(prime)): 
     result = sub(result) 
    return result 

Answer 2

我不會調試你的代碼你，但我會盡力回答您的具體問題：

，但我不能換我的頭周圍 有必要的遞歸思維它跟蹤所有的路徑，並把它們整齊地在一個列表：

爲了讓遞歸函數收集其結果到列表中，你需要做這樣的事情：

def _myfn(data, res): 
    if (..recurse..): 
     return _myfn(data2, res + [item]) # item being the result of this iteration 
    else: 
     # terminal case 
     return res 

def myfn(data): 
    return _myfn(data, []) 

您能夠壓制這些成一個功能：

def myfn(data, res=None): 
    if res is None: 
     res = [] 
    if (..recurse..): 
     return myfn(data2, res + [item]) 
    else: 
     # terminal case 
     return res 

，或者你可以讓_myfn本地myfn：

def myfn(data): 
    def _myfn(data, res): 
     if (..recurse..): 
      return _myfn(data2, res + [item]) 
     else: 
      # terminal case 
      return res 
    return _myfn(data, []) 

當涉及到包裝你的頭周圍的遞歸思維，只記得（1）總處理基礎案例;-)和（2）在每個遞歸中首先（i）產生所有可能的後續步驟，然後（ii）然後對每個步驟進行遞歸。爲（i）寫一個單獨的函數通常會稍微清除一些代碼。

作爲該發現從根的所有路徑葉二叉樹（略教學法編碼）遞歸函數的例子 - 這就是你想要做的..：

# tree = (root, left, right) 

def all_paths(t): 
    leaf_paths = [] 

    def _all_paths(t, res): 
     root, left, right = t 

     # calculate all next-steps 
     next_steps = [step for step in [left, right] if step] 

     if not next_steps: 
      # handle base case (found one solution) 
      leaf_paths.append(res + [root]) 
     else: 
      # recurse 
      for step in next_steps: 
       _all_paths(step, res + [root]) 

    _all_paths(t, []) 

    return leaf_paths 

>>> all_paths((2,(),())) 
[[2]] 
>>> all_paths(
... (2, 
... (3,(),()), 
... (4,(),()))) 
[[2, 3], [2, 4]] 

和該圖

>>> t = (
    2, 
    (7, 
    (2,(),()), 
    (6, 
     (5,(),()), 
     (11,(),()))), 
    (5, 
    (), 
     (9, 
     (4,(),()), 
     ()))) 
>>> print all_paths(t) 
[[2, 7, 2], [2, 7, 6, 5], [2, 7, 6, 11], [2, 5, 9, 4]] 

Answer 3

import math 

def test(x, curr, acc): 
    if x < 10: 
     acc.append(curr) 
     return 
    for i in range(int(math.log(x,10))+1,0,-1): 
     k = int(x/(math.pow(10,i))) * math.pow(10,i-1) + (x % math.pow(10,i-1)) 
     if isPrime(k): 
      next = list(curr) 
      next.append(int(k)) 
      test(k, next, acc) 

東西像這樣應該是k是累加器。你可以添加其他功能，使通話更方便：

def getTraces(prime): 
    traces = [] 
    test(prime, [prime], traces) 
    return traces 

Answer 4

看起來你找到你的解決方案，但考慮到你的定義有質數永遠不能deletables，像11或911或1601，因爲無論我做什麼，永遠達不到一個位質，我不在你的代碼看到，考慮所以這裏是我對，使用遞歸和itertools：

import itertools 

def isDeletablePrime(n,*,valor=True): 
    if isPrime(n): 
     N = str(n) 
     S = len(N) 
     if S>1 and any(p in N for p in "2 3 5 7".split()) : 
      resul = list() 
      for num in set(map(lambda x: int("".join(x)), itertools.combinations(N,S-1))): #set(...) eliminate potencial duplicates like with 331 there are 2 way to get 31, removing the firts or second 3 
       temp = isDeletablePrime(num,valor=True) 
       if temp: 
        resul.extend((n,)+tt for tt in temp) 
      if valor: 
       return tuple(filter(lambda r:len(r)==S, resul)) 
      else: 
       return any(len(r)==S for r in resul) 
     elif n in {2,3,5,7}: #base case 
      return ((n,),) if valor else True 
    return tuple() if valor else False #base case and default 

print(3301,"->", isDeletablePrime(3301)) 
print(3793,"->", isDeletablePrime(3793)) 
print(1601,"->", isDeletablePrime(1601)) 

這可以作爲一個謂語和一個功能我做這種方式的不特殊原因