我使用长度为N的自然数和条目之和的向量，例如(N，S)=(4,7)一个示例向量E=[1，2，1，3]其中假设向量中的所有条目>0。
我想列出所有具有相同配置的向量(N，S)=(4,7)，但旋转应该被过滤掉。
问题：什么是最好的算法
(我的实际实现是在Pari/GP中，它使用上下索引值的边界向量提供嵌套for循环)
我已经尝试了第一个"；暴力"；解决方案，因为我使用嵌套的for循环生成了一个列表，但将两个concat(E，E)连接的向量存储在列表EE[]中，然后，对于每个新向量E=[e1，E_2，E_3，E_4][/em>检查该向量是否出现在已检查列表EE[]中的连接向量中，如果不是，则将其附加为新的有效条目
EE[k]=E|E=[E_1，E_2，E_3，E_4，E_1，E_2，E_4]。这里的比较类似于字符串比较-如果匹配开始于位置1或直到N，则总是找到匹配。
这种方法有效，但在我看来有点像蛮力，并且由于其组合结构，随着N和S的增加而爆炸。
是否存在更好的方法
注意：目标语言是Pari/GP
注：伪算法就足够了，但Pari/GP中的工具可能允许一些更紧凑的解决方案/表示法
示例，(N，S)=(4,7)
以下是一个非常简单的示例。
假设通过嵌套循环，我以以下方式获得向量E：
[1,1,1,4] --- first vector: store as [1,1,1,4;1,1,1,4] in EE
[1,1,2,3] --- 2nd vector: not in EE so far, append as [1,1,2,3;1,1,2,3] to EE
[1,2,1,3] ...
[2,1,1,3] ...
[1,1,3,2] --- ignore!! This is a rotation of an earlier entry (is in EE)
[1,2,2,2]
...
这依次构建向量列表EE:
[1,1,1,4;1,1,1,4]
[1,1,2,3;1,1,2,3]
[1,2,1,3;1,2,1,3]
[2,1,1,3;2,1,1,3]
[1,2,2,2;1,2,2,2]
这个列表，只包含前N列，是我以后要处理的向量列表。
附加健全性检查：对于(N，S)=(4,16)，在删除旋转后，我得到未筛选列表length_unfiltered=455和length_filtered=116。
有一种众所周知的算法可以生成删除了旋转的字符串(在组合数学中通常称为项链)。该算法在恒定的摊销时间内工作，这意味着可以在恒定的时间内去除旋转的等价物。
Frank Rusky称这种算法为FKM算法。它在中进行了描述https://people.engr.ncsu.edu/savage/AVAILABLE_FOR_MAILING/necklace_fkm.pdf.(还有其他几篇论文，以及Rusky的《组合世代》一书的第7.2章)。
实现是直接的(但在PARI中编码需要几个小时，所以现在我要离开)。给定和的附加要求可以毫无困难地结合到算法中。
一个效率较低的替代方案是生成所有(N，S)个单词，然后过滤掉那些不是项链的单词。对于生成部分，有内置的PARI函数forpart和forperm。滤波可以使用FKM算法的简化自适应来完成。由于只需要一个测试，所以在这个测试中可以避免回溯和递归。
部分PARI代码如下：下面的PARI可以用于生成长度为n和总和为s的所有向量。此方法避免了递归，并为每个解决方案调用act。
forsumset(n, s, act)={
my(w=vector(n), p=1);
while(p > 0,
if(s>n-p, w[p]++; s--; if(p==n-1, w[n]=s;act(w), p++), s+=w[p]; w[p]=0; p--);
);
}
示例用法：
local(total=0); forsumset(4, 16, w->total++); total
按预期给出455。
以下函数是使用FKM算法对项链特性的测试：
isnecklace(w)={
my(d=1);
for(p=2, #w, my(e=w[p]-w[p-d]); if(e<0, return(0)); if(e>0, d=p));
#w%d==0
}
示例用法：
local(total=0); forsumset(4,16,w->if(isnecklace(w), total++)); total
按预期给出116。
更新
下面将这两个想法结合到一个单独的算法中，该算法以摊余常数时间计算每个新术语。由于结果的数量是指数依赖于s的，所以总时间仍然是指数的。如果只需要计算条目的总数，那么有更快的方法。
forneck(n, s, act)={
my(w=vector(n), ds=vector(n), p=1, d=1);
while(p > 0,
if(w[p],
w[p]++; s--; d=p,
my(e=if(p==1,1,w[p-d])); w[p]=e; s-=e);
if(s>=n-p,
if(p==n, if(s, w[n]+=s; s=0; d=p); if(p%d==0, act(w)), p++; ds[p]=d),
d=ds[p]; s+=w[p]; w[p]=0; p--);
);
}
示例用法：
local(total=0); forneck(4,16,w->total++); total
按预期给出116。
这只是对Andrew答案的评论，而不是一个"回答"；，但是对于评论框来说太长了
Andrew的例程允许快速生成小(N，s)=(2,2)到(16,16)的过滤版本的统计数据。它给出了一个我迄今为止从未见过的数字组合三角形。(可能第一列应该填写一个)
也许值得在OEIS中输入…-嗯，它在OEIS中是：-)
我得到了：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 -> N
--+----------------------------------------------------------------------
1 | 0 . . . . . . . . . . . . . . .
2 | 0 1 . . . . . . . . . . . . . .
3 | 0 1 1 . . . . . . . . . . . . .
4 | 0 2 1 1 . . . . . . . . . . . .
5 | 0 2 2 1 1 . . . . . . . . . . .
6 | 0 3 4 3 1 1 . . . . . . . . . .
7 | 0 3 5 5 3 1 1 . . . . . . . . .
8 | 0 4 7 10 7 4 1 1 . . . . . . . .
9 | 0 4 10 14 14 10 4 1 1 . . . . . . .
10 | 0 5 12 22 26 22 12 5 1 1 . . . . . .
11 | 0 5 15 30 42 42 30 15 5 1 1 . . . . .
12 | 0 6 19 43 66 80 66 43 19 6 1 1 . . . .
13 | 0 6 22 55 99 132 132 99 55 22 6 1 1 . . .
14 | 0 7 26 73 143 217 246 217 143 73 26 7 1 1 . .
15 | 0 7 31 91 201 335 429 429 335 201 91 31 7 1 1 .
16 | 0 8 35 116 273 504 715 810 715 504 273 116 35 8 1 1
|
|
v
S