识别索引向量上的循环；制作列表，减去旋转次数

Question

我使用长度为N的自然数向量和条目总和S，例如，(N,S)=(4,7)一个示例向量 E=[1,2,1,3] 其中所有条目向量中假设> 0。

我想列出具有相同配置(N,S)=(4,7)的所有向量，但应过滤掉旋转。

问题：最好的算法是什么？
（我的实际实现是在 Pari/GP 中，它提供了一个嵌套的 for 循环，使用下限和上限索引值的边界向量）

我首先尝试了一个“强力”解决方案，因为我使用嵌套的 for 循环生成一个列表，但将向量连接的双重concat(E,E)存储在列表EE[]中，然后，对于每个新向量E=[e_1,e_2,e_3,e_4]检查该向量是否出现在已检查列表EE[]中的串联向量中，如果没有则将其附加为新的有效条目
EE[k]=E||E = [e_1,e_2,e_3,e_4,e_1,e_2,e_3,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 。

Answer 1

有一种众所周知的算法可以生成删除了旋转的字符串（通常在组合学中称为项链）。该算法在恒定的摊销时间内工作，这意味着可以在恒定的时间内删除旋转的等价物。

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 可用于生成 lengthn和 sum的所有向量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。