algorithm - 列出条目总和为 n 的所有 k 元组，忽略旋转

Question

是否有一种有效的算法可以找到总和为 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) 都在输出列表中。

编辑:添加了粗体说明。我很抱歉没有像我在原始帖子中那样清楚地说明这些问题。

Answer 1

您可以先将分区(完全忽略顺序)生成为元组 (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?

希望对您有所帮助。