python - 递归生成所有位和为 n 的 k 位数字
问题描述
我正在解决一个问题,我正在寻找所有 k 位数字,其数字总和给定的 n。
我找到了如何做到这一点并将其作为整数分区问题来处理,但是我希望能够只输入 n 和 k 数字(没有 max_element)但是当我尝试从代码中删除它时它似乎不起作用了。
我怎样才能改变它加上反转它?
def c(n, k, max_element):
allowed = range(max_element, 0, -1)
def helper(n, k, t):
if k == 0:
if n == 0:
yield t
elif k == 1:
if n in allowed:
yield t + (n,)
elif 1 * k <= n <= max_element * k:
for v in allowed:
yield from helper(n - v, k - 1, t + (v,))
return helper(n, k, ())
for p in c(5, 3, 3):
print(p)
我尝试使用反向方法,但显然它在生成器中不起作用。
结果:
(3, 1, 1)
(2, 2, 1)
(2, 1, 2)
(1, 3, 1)
(1, 2, 2)
(1, 1, 3)
预期结果:
113 122 131 212 221 311
解决方案
这里有几个问题;首先是您希望按顺序排列数字,并且此代码以相反的顺序生成它们,因为range(max_element, 0, -1)
. 另一个问题是,由于您正在生成数字,因此最小元素应为 0,最大元素应始终为 9。我们可以通过将范围更改为range(10)
.
我们仍然需要注意不要生成以 0 开头的数字,因此我们将创建allowed
一个参数并range(1, 10)
仅用于第一个数字。我还对其进行了更改,以将结果作为整数而不是元组返回。
作为参考,这个生成器函数的代码来自我对另一个问题的回答。
def c(n, k):
def helper(n, k, t, allowed):
if k == 0:
if n == 0:
yield t
elif k == 1:
if n in allowed:
yield 10*t + n
elif 0 <= n <= 9 * k:
for v in allowed:
yield from helper(n - v, k - 1, 10*t + v, range(10))
return helper(n, k, 0, range(1, 10))
例子:
>>> for p in c(5, 3):
... print(p)
...
104
113
122
131
140
203
212
221
230
302
311
320
401
410
500
推荐阅读
- java - 使用 oracle 作为数据库打包 Spring Boot 应用程序
- php - 每次我尝试使用 Swift 和 Alamofire 将数据发布到 MySQL 数据库时,数据显示为空?
- javascript - 从rest api获取数据并在html页面中以table的形式打印出来
- logstash - Logstash 中的 Grok 模式格式
- c# - 如何在c#中将动态文本从英语翻译成西班牙语
- mysql - 如何最小化sql查询
- continuous-integration - Chef 服务器可以有多个工作站吗?
- powershell - 在第一个进程完成后运行两个自动退出批处理而不退出命令提示符
- python - 使用 Python 解析 YAML 文件,以提取唯一/非唯一关键字对之间的文本块
- python - 使用 python 将自动录音转换为文本