跟踪可删除素数的递归函数 - Python 3
Recursive Function For Tracing Deletable Primes - Python 3
可删除质数是一种质数，可以按特定顺序删除其数字以始终创建质数，并最终以一位数质数结束。例如，3301 是一个可删除素数，因为它可以这样操作：3301 -> 331 -> 31 -> 3。我正在尝试在 Python 中编写一个递归函数，该函数将可删除素数的所有路径追溯到其个位数根，但我完全被卡住了。它已经超出了我的理解范围，我什至无法再遵循自己的代码了。该函数所需输出的完整示例类似于 getTraces(3793) returns [[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]]
这是我拥有的功能的当前版本（如果有帮助的话）。我试图将它变成 return 一个包含单个数字质数的所有可能路径的列表，但我无法围绕让它跟踪所有路径并将它们整齐地放入所需的递归思维来思考列表：
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
这个函数只是 return 一个素数所有父项的列表（删除一位数字的所有可能素数），并在 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
我不会为您调试代码，但我会尽力回答您的具体问题：
but I can't wrap my head around the recursive thinking necessary to
have it trace all the paths and put them neatly in a list:
要使递归函数将其结果收集到列表中，您需要执行如下操作：
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]]
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
我终于能够解决我的问题，所以我想我也可以 post 我的答案，因为我无法删除问题。我最终放弃了递归地尝试，因为我想出了一种无需递归的方法，但我感谢大家提供的帮助和指导。这是我的解决方案：
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
看起来你找到了你的解决方案，但根据你的定义，有一些质数永远不能删除，比如 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) )
this 可以用作谓词和函数，我这样做没有任何特殊原因
可删除质数是一种质数，可以按特定顺序删除其数字以始终创建质数，并最终以一位数质数结束。例如，3301 是一个可删除素数，因为它可以这样操作：3301 -> 331 -> 31 -> 3。我正在尝试在 Python 中编写一个递归函数，该函数将可删除素数的所有路径追溯到其个位数根，但我完全被卡住了。它已经超出了我的理解范围，我什至无法再遵循自己的代码了。该函数所需输出的完整示例类似于 getTraces(3793) returns [[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]]
这是我拥有的功能的当前版本（如果有帮助的话）。我试图将它变成 return 一个包含单个数字质数的所有可能路径的列表，但我无法围绕让它跟踪所有路径并将它们整齐地放入所需的递归思维来思考列表：
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
这个函数只是 return 一个素数所有父项的列表（删除一位数字的所有可能素数），并在 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
我不会为您调试代码，但我会尽力回答您的具体问题：
but I can't wrap my head around the recursive thinking necessary to have it trace all the paths and put them neatly in a list:
要使递归函数将其结果收集到列表中，您需要执行如下操作：
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]]
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
我终于能够解决我的问题，所以我想我也可以 post 我的答案，因为我无法删除问题。我最终放弃了递归地尝试，因为我想出了一种无需递归的方法，但我感谢大家提供的帮助和指导。这是我的解决方案：
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
看起来你找到了你的解决方案，但根据你的定义，有一些质数永远不能删除，比如 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) )
this 可以用作谓词和函数，我这样做没有任何特殊原因