列出所有k元组与项相加为n，忽略旋转 [英] List all k-tuples with entries summing to n, ignoring rotations
问题描述
是否有一个有效的算法寻找的 K 的非负整数的总和所有序列的 N 的，同时避免旋转（完全，如果可能的话）？ 的顺序问题，但旋转是多余的了我工作的问题。
Is there an efficient algorithm for finding all sequences of k non-negative integers that sum to n, while avoiding rotations (completely, if possible)? The order matters, but rotations are redundant for the problem I'm working on.
例如，用的 K = 3和 N 的= 3，我希望得到类似下面的列表：
For example, with k = 3 and n = 3, I would want to get a list like the following:
（3，0,0），（2，1,0），（2，0,1），（1，1，1）。
(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 的
The tuple (0, 3, 0) should not be on the list, since it is a rotation of (3, 0, 0). However, (0, 3, 0) could be in the list instead of (3, 0, 0). Note that both (2, 1, 0) and (2, 0, 1) are on the list -- I do not want to avoid all permutations of a tuple, just rotations. Additionally, 0 is a valid entry -- I am not looking for partitions of n.
我现在的程序循环结束1＆LT; =的我的＆LT; =的 N 的，设置的第一个条目等于的我的，然后递归地解决这个问题的 N' = N 的 - 的我和 K' = K - 1。我得到一些加速通过强制，没有条目是严格比第一次更大，但这种方法仍然会产生大量的旋转 - 例如，给定的 N 的= 4的 K 的= 3，两者（2,2,0）和（2,0,2）是在输出列表
My current procedure is to loop from over 1 <= i <= n, set the first entry equal to i, and then recursively solve the problem for n' = n - i and k' = k - 1. I get some speed-up by mandating that no entry is strictly greater than the first, but this approach still generate a lot of rotations -- for example, given n = 4 and k = 3, both (2,2,0) and (2,0,2) are in the output list.
编辑：粗体加说明。我不使这些问题清楚我应该在原岗位道歉。
Added clarifications in bold. I apologize for not making these issues as clear as I should have in the original post.
推荐答案
您可以先产生分区（这完全忽略顺序）作为一个元组（X_1，X_2，...，x_n）
You can first generate the partitions (which ignore order completely) as a tuple (x_1, x_2, ..., x_n)
其中，x_i =的时候，我会出现数。
where x_i = number of times i occurs.
所以我总和* x_i = N
So Sum i* x_i = n.
我相信你已经知道如何做到这一点（从您的意见）。
I believe you already know how to do this (from your comments).
一旦你有一个分区，现在就可以生成排列此（它看作一个多集{1,1，...，2,2 ...，... N}，其中i出现x_i倍），它忽略了旋转，使用回答这个问题：
Once you have a partition, you can now generate the permutations for this (viewing it as a multiset {1,1,...,2,2...,...n}, where i occurs x_i times) which ignore rotations, using the answer to this question:
<一个href="http://stackoverflow.com/questions/3467914/is-there-an-algorithm-to-generate-all-unique-circular-permutations-of-a-multiset">http://stackoverflow.com/questions/3467914/is-there-an-algorithm-to-generate-all-unique-circular-permutations-of-a-multiset
希望有所帮助。
这篇关于列出所有k元组与项相加为n，忽略旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
