是否有一种有效的算法,可以找到所有不重复的长度为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)。
注:在粗体字中添加了澄清。我很抱歉没有在原始帖子中表述得更清楚。
例如,当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)。
注:在粗体字中添加了澄清。我很抱歉没有在原始帖子中表述得更清楚。