列出所有 k 元组，其中条目总和为 n，忽略旋转

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

您可以对解决方案进行排序并消除旋转。
或
您可以尝试使您的递归解决方案构建只能如何排序的元组

？这是我快速编造的东西

static list<tuple> tups;
void recurse(tuple l, int n, int k, int m)
{
  if (k == 0 && n == 0)
  {
    tups.add(l);
    return;
  }
  if (k == 0)
    return;

  if (k*m > n) //prunes out tuples that could not possibly be sorted
    return;
  else
    for(int x = m; x <= n; x++)
      recurse(l.add(x), n-x, k-1, x); //try only tuples that are increasing
}

，用 m = 0 和一个空列表作为初始步骤。

这是一个 C# 控制台应用程序实现： http://freetexthost.com/b0i05jkb4e

哦，我看到我的旋转假设的错误，我认为你只是指排列，而不是实际的旋转。
但是，您可以扩展我的解决方案以创建唯一递增元组的非旋转排列。我现在正在努力

Answer 2

您需要按字典顺序生成整数分区。

这里是一篇非常好的论文，具有快速算法。

HTH。

请注意，CAS 程序通常实现这些功能。例如在 Mathematica 中：

Innput: IntegerPartitions[10, {3}]
Output: {{8, 1, 1}, {7, 2, 1}, {6, 3, 1}, 
         {6, 2, 2}, {5, 4, 1}, {5, 3, 2}, 
         {4, 4, 2}, {4, 3, 3}}

Answer 3

您可以首先将分区（完全忽略顺序）生成为元组 (x_1, x_2, ..., x_n)，

其中 x_i = i 出现的次数。

所以求和 i* x_i = n。

我相信您已经知道如何做到这一点（根据您的评论）。

一旦有了分区，您现在就可以为此生成排列（将其视为多重集 {1,1,...,2,2...,...n}，其中 i 出现 x_i 次），该排列忽略旋转，使用这个问题的答案：

是否有一种算法可以生成多重集的所有唯一循环排列？

希望有帮助。