用于追踪可删除素数的递归函数 - 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)) 

这可以作为一个谓语和一个功能我做这种方式的不特殊原因