如何在Python中返回递归函数的列表 [英] How to return a list of a recursive function in Python
问题描述
我正在尝试从该函数返回一个字符串列表,该函数计算所有不连续为0的可能性排列.
I'm trying to return a list of strings from the function that calculate all possibilites permutations without consecutives 0.
为此,我正在运行一个有效的递归函数,但是我需要创建一个包含结果的列表.
To do this, I'm running a recursive function that works, but I need to create a list with the results.
# Function to print all n–digit binary strings without any consecutive 0's
def countStrings(n, out="", last_digit=0):
# if the number becomes n–digit, print it
if n == 0:
print(out)
return
# append 0 to the result and recur with one less digit
countStrings(n - 1, out + '1', 0)
# append 1 to the result and recur with one less digit
# only if the last digit is 0
if last_digit == 0:
countStrings(n - 1, out + '0', 1)
当我运行它时,例如: a = countStrings(3)
,它将打印所有可能的变量,但变量"a"还原为无":
When I run it eg: a = countStrings(3)
, it print all possibilits but the variable "a" returs as "None":
结果:
111
110
101
011
010
type(a): Nonetype
我试图在某些地方插入一个附录,但是没有结果
I've tried to insert an append in some places, but with no result
我不知道我缺少什么
推荐答案
解决方案A
我建议将程序的关注点分解为多个功能-
I would suggest separating the program's concerns into multiple functions -
def binaries(n):
for m in range(2 ** n):
yield f"{m:>0{n}b}"
print(list(binaries(3)))
['000', '001', '010', '011', '100', '101', '110', '111']
现在我们可以编写 pairwise
,它在可迭代对象上成对迭代-
Now we can write pairwise
which iterates pairwise over an iterable -
from itertools import tee, islice
def pairwise(t):
a, b = tee(t)
yield from zip(a, islice(b, 1, None))
print(list(pairwise("011001")))
[('0', '1'), ('1', '1'), ('1', '0'), ('0', '0'), ('0', '1')]
现在很容易将 solution
实施为大小为 n
的所有 binaries
的组合,其中 pairwise
分析任何特定的二进制不包含两个相邻的零-
Now it's easy to implement solution
as a combination of all binaries
of size n
where pairwise
analysis of any particular binary does not contain two adjacent zeroes -
def solution(n):
for b in binaries(n):
for p in pairwise(b):
if p == ('0','0'):
break
else:
yield b
print(list(solution(3)))
['010', '011', '101', '110', '111']
如果所有人只想计算解决方案的数量,我们可以编写 count_solutions
作为 solutions
-
If all only want a count of the solutions, we can write count_solutions
as a specialisation of solutions
-
def count_solutions(n):
return len(list(solution(n)))
print(count_solutions(3))
5
让我们看一下它在一个更大的示例中的作用, n
= 8-
Let's see it work on a larger example, n
= 8 -
print(list(solutions(8)))
print(count_solutions(8))
['01010101', '01010110', '01010111', '01011010', '01011011', '01011101', '01011110', '01011111', '01101010', '01101011', '01101101', '01101110', '01101111', '01110101', '01110110', '01110111', '01111010', '01111011', '01111101', '01111110', '01111111', '10101010', '10101011', '10101101', '10101110', '10101111', '10110101', '10110110', '10110111', '10111010', '10111011', '10111101', '10111110', '10111111', '11010101', '11010110', '11010111', '11011010', '11011011', '11011101', '11011110', '11011111', '11101010', '11101011', '11101101', '11101110', '11101111', '11110101', '11110110', '11110111', '11111010', '11111011', '11111101', '11111110', '11111111']
55
解决方案B
我一直在考虑这个问题,我不喜欢上面的解决方案中的数字在比较之前如何转换为字符串.
I've been thinking about this problem a little more and I didn't like how the numbers in the solution above are converted to strings before comparison.
首先,我们按位编写
-
def bitwise(n, e):
if e == 0:
return
else:
yield from bitwise(n >> 1, e - 1)
yield n & 1
for n in range(2 ** 3):
print(tuple(bitwise(n, 3)))
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
然后成对
-
from itertools import tee, islice
def pairwise(t):
a, b = tee(t)
yield from zip(a, islice(b, 1, None))
for n in range(2 ** 3):
print(bin(n), list(pairwise(bitwise(n, 3))))
0b0 [(0, 0), (0, 0)]
0b1 [(0, 0), (0, 1)]
0b10 [(0, 1), (1, 0)]
0b11 [(0, 1), (1, 1)]
0b100 [(1, 0), (0, 0)]
0b101 [(1, 0), (0, 1)]
0b110 [(1, 1), (1, 0)]
0b111 [(1, 1), (1, 1)]
最后 solution
-
def solution(e):
for n in range(2 ** e):
for p in pairwise(bitwise(n, e)):
if p == (0, 0):
break
else:
yield n
sln = list(map(bin, solution(3)))
print(sln)
print(len(sln))
['0b10', '0b11', '0b101', '0b110', '0b111']
5
和 n
= 8-
sln = list(map(bin, solution(8)))
print(sln)
print(len(sln))
['0b1010101', '0b1010110', '0b1010111', '0b1011010', '0b1011011', '0b1011101', '0b1011110', '0b1011111', '0b1101010', '0b1101011', '0b1101101', '0b1101110', '0b1101111', '0b1110101', '0b1110110', '0b1110111', '0b1111010', '0b1111011', '0b1111101', '0b1111110', '0b1111111', '0b10101010', '0b10101011', '0b10101101', '0b10101110', '0b10101111', '0b10110101', '0b10110110', '0b10110111', '0b10111010', '0b10111011', '0b10111101', '0b10111110', '0b10111111', '0b11010101', '0b11010110', '0b11010111', '0b11011010', '0b11011011', '0b11011101', '0b11011110', '0b11011111', '0b11101010', '0b11101011', '0b11101101', '0b11101110', '0b11101111', '0b11110101', '0b11110110', '0b11110111', '0b11111010', '0b11111011', '0b11111101', '0b11111110', '0b11111111']
55
建议阅读
如果您从未在Python中看到过用于..else 的循环,请阅读有关此出色构造的文档
If you've never seen a for..else
loop in Python, please read the docs about this wonderful construct
这篇关于如何在Python中返回递归函数的列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!