识别索引向量上的循环；制作清单，减去旋转

Question

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

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

Question: what is the best algorithm?
(my practical implementation is in Pari/GP which provides a nested for-loop using a vector of bounds for lower and upper index value)

我首先尝试了一种“蛮力”解决方案，因为我使用嵌套的 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.

Does a better method exist?

注意：目标语言是Pari/GP
注意：伪算法就足够了 - 但也许 Pari/GP 中的工具允许一些更紧凑的 solutions/notation.

例如，(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 章 'Combinatorial Generation'）。

实施很简单（但在 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。

Answer 2

这只是对安德鲁回答的评论，不是“回答”，但对于评论框来说太长了。

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

识别索引向量上的循环；制作清单，减去旋转

Identify loops over a vector of indices; make list, minus rotations

c

filtering

nested-loops

pari

pari-gp