是否有一种有效的算法可以找到总和为 n 的所有 k 非负整数序列,同时避免旋转(如果可能,完全避免)? 顺序很重要,但轮换对于我正在处理的问题来说是多余的。
例如,k = 3 和 n = 3,我想得到如下列表:
(3, 0, 0), (2, 1, 0), (2, 0, 1), (1, 1, 1).
元组 (0, 3, 0) 不应该在列表中,因为它是 (3, 0, 0) 的旋转。但是,(0, 3, 0) 可能在列表中而不是 (3, 0, 0)。请注意,(2, 1, 0) 和 (2, 0, 1) 都在列表中——我不想避免元组的所有排列,只是旋转。此外,0 是一个有效条目 -- 我不是在寻找 n 的分区。
我目前的程序是从 1 <= i <= n 开始循环,将第一个条目设置为 i,然后递归求解 n' = n - i 和 k' = k - 1. 通过规定没有条目严格大于第一个条目,我得到了一些加速,但这种方法仍然会产生很多旋转——例如,给定 n = 4 和 k = 3, (2,2,0) 和 (2,0,2) 都在输出列表中。
编辑:添加了粗体说明。我很抱歉没有像我在原始帖子中那样清楚地说明这些问题。
最佳答案
您可以先将分区(完全忽略顺序)生成为元组 (x_1, x_2, ..., x_n)
其中 x_i = i 出现的次数。
所以 Sum i* x_i = n。
我相信您已经知道如何执行此操作(根据您的评论)。
有了分区后,您现在可以为此生成排列(将其视为多重集 {1,1,...,2,2...,...n},其中 i 出现 x_i 次) 忽略旋转,使用这个问题的答案:
Is there an algorithm to generate all unique circular permutations of a multiset?
希望对您有所帮助。
关于algorithm - 列出条目总和为 n 的所有 k 元组,忽略旋转,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3731705/