列出所有元素之和为n的k元组，忽略旋转。

Question

列出所有元素之和为n的k元组，忽略旋转。

4

是否有一种有效的算法，可以找到所有不重复的长度为k的非负整数序列，使它们的和为n，并且避免旋转（如果可能的话完全避免）？顺序很重要，但对于我正在解决的问题来说，旋转是多余的。

例如，当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)。

注：在粗体字中添加了澄清。我很抱歉没有在原始帖子中表述得更清楚。

- Seth

你正在寻找n的分区，但大小最多为k。并插入零以填满k个空间。 - Dr. belisarius

我认为最好的方法是计算所有总和为n的无序集合，然后找到那些集合中避免旋转的所有唯一序列。 - Kirk Broadhurst

@belisarius：找到所有大小不超过 k 的 n 的分区是问题的一部分，但并不是全部。严格地讲，如果总和的加数的顺序被置换，则两个分区相同。我并不难计算分区，甚至所有加数的排列组合--问题在于找到所有旋转的排列组合。 - Seth

@Kirk -- 没错。只是我还没有找到一种有效的方法来完成后半部分。 - Seth

3个回答

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

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

- Jean-Bernard Pellerin

1

感谢您的回复。如果我理解正确，我认为“仅尝试递增的元组”部分是无效的。例如，对于k = 4，n = 6，元组（1,2,1,2）应该是输出的一部分，但这个元组的旋转没有任何递增的。 - Seth

1

你需要按字典顺序生成整数划分。这里有一个非常好的论文，提供快速算法。

希望这可以帮到你。

请注意， 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}}

- Dr. belisarius

你和Jean在他的回答中有同样的误解。 - Nikita Rybak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

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

其中 x_i = i 出现的次数。

因此，Sum i * x_i = n。

我相信您已经知道如何做到这一点（从您的评论中可以看出）。

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

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

希望这有所帮助。