擅长:python、mysql、java
<p>这是一个基于生成器的尝试,它只是一次生成一个置换,而不是将它们全部存储在内存中。我使用了生成器方法,因为我认为任何其他方法都会耗尽内存,只要<code>k</code>大于5,排列的数量就会很大:</p>
<pre><code>def find_perm(k, n, N=None):
# Initialize N
if N is None:
N = list(range(1, n - k + 1))
if k == 0:
return []
# Only search up to n (the current target)
for i in N[:(n + 1)]:
if i > n:
continue
if i == n:
yield [i]
continue
# Recurse
sub_perms = find_perm(k - 1, n - i, N[:(n + 1)])
for sub_perm in sub_perms:
perm = [i] + sub_perm
if sum(perm) == n:
yield perm
</code></pre>
<p>输出示例:</p>
<pre><code>list(find_perm(2, 6))
# [[2, 4], [3, 3], [4, 2]]
# Too many to store, just printing a few
big_perms = find_perm(10, 100)
for i in range(5):
print(next(big_perms))
# [1, 1, 1, 1, 1, 1, 1, 1, 2, 90]
# [1, 1, 1, 1, 1, 1, 1, 1, 3, 89]
# [1, 1, 1, 1, 1, 1, 1, 1, 4, 88]
# [1, 1, 1, 1, 1, 1, 1, 1, 5, 87]
# [1, 1, 1, 1, 1, 1, 1, 1, 6, 86]
</code></pre>