英文:
efficient way to generate non-increasing integer sequence of length n, with each element bounded between j and k
问题
I need to write a function that generate non-increasing integer sequence of length n, with each element bounded between j and k (inclusive).
我需要编写一个函数，生成长度为n的非递增整数序列，其中每个元素限制在j和k之间（包括j和k）。
i.e. if n = 3, j = 0 and k = 3:
例如，如果n = 3，j = 0，k = 3：
[(3,3,3), (3,3,2), (3,3,1), (3,3,0), (3,2,2), (3,2,1), (3,2,0), (3,1,1), (3,1,0), ... , (1,1,1), (1,1,0), (1,0,0), (0,0,0)]
if n is small, I would just use nested for loops, but in case n is very large, I would like to know if there is an efficient method to get such list.
如果n很小，我可以简单地使用嵌套的for循环，但如果n很大，我想知道是否有一种高效的方法来获取这样的列表。
I was thinking of using itertools, but I am not too sure how.
我考虑使用itertools，但我不太确定如何使用。
英文:
I need to write a function that generate non-increasing integer sequence of length n, with each element bounded between j and k (inclusive)
i.e. if n = 3, j = 0 and k = 3:
[(3,3,3), (3,3,2), (3,3,1), (3,3,0), (3,2,2), (3,2,1), (3,2,0), (3,1,1), (3,1,0), ... , (1,1,1), (1,1,0), (1,0,0), (0,0,0)]
if n is small, I would just use nested for loops, but in case n is very large, I would like to know if there is an efficient method to get such list.
I was thinking of using itertools, but I am not too sure how.
答案1
得分: 2
以下是翻译好的代码部分：
使用itertools.combinations_with_replacement最简单，然后反转元素：
from itertools import combinations_with_replacement
def func(n, j, k):
for c in combinations_with_replacement(range(j, k+1), n):
yield c[::-1]
示例：
>>> list(func(3, 0, 3))
[(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (1, 1, 0), (2, 1, 0), (3, 1, 0), (2, 2, 0), (3, 2, 0), (3, 3, 0),
(1, 1, 1), (2, 1, 1), (3, 1, 1), (2, 2, 1), (3, 2, 1), (3, 3, 1), (2, 2, 2), (3, 2, 2), (3, 3, 2), (3, 3, 3)]
另一种更简洁的方法是按建议提供的顺序反转可迭代对象：
def func(n, j, k):
return combinations_with_replacement(range(k, j-1, -1), n)
示例：
>>> list(func(3, 0, 3))
[(3, 3, 3), (3, 3, 2), (3, 3, 1), (3, 3, 0), (3, 2, 2), ...
还有一个递归手写实现，仅供娱乐：
def func(n, j, k):
if not n:
return [[]]
result = []
for i in range(k, j-1, -1):
for comb in func(n-1, j, i):
result.append([i] + comb)
return result
示例：
>>> func(2, 0, 2)
[[2, 2], [2, 1], [2, 0], [1, 1], [1, 0], [0, 0]]
英文:
The easiest would be to use itertools.combinations_with_replacement and reverse the elements:
from itertools import combinations_with_replacement
def func(n, j, k):
for c in combinations_with_replacement(range(j, k+1), n):
yield c[::-1]
>>> list(func(3, 0, 3))
[(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0), (1, 1, 0), (2, 1, 0), (3, 1, 0), (2, 2, 0), (3, 2, 0), (3, 3, 0),
(1, 1, 1), (2, 1, 1), (3, 1, 1), (2, 2, 1), (3, 2, 1), (3, 3, 1), (2, 2, 2), (3, 2, 2), (3, 3, 2), (3, 3, 3)]
As suggested in the comments (thx @CrazyChucky), providing the the iterable in reverse order makes this even more concise and produces the sequences in your suggested order:
def func(n, j, k):
return combinations_with_replacement(range(k, j-1, -1), n)
>>> list(func(3, 0, 3))
[(3, 3, 3), (3, 3, 2), (3, 3, 1), (3, 3, 0), (3, 2, 2), ...
And just for the LOLs, here is a recursive hand-written implementation:
def func(n, j, k):
if not n:
return [[]]
result = []
for i in range(k, j-1, -1):
for comb in func(n-1, j, i):
result.append([i] + comb)
return result
>>> func(2, 0, 2)
[[2, 2], [2, 1], [2, 0], [1, 1], [1, 0], [0, 0]]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论