3

我使用长度为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 。

4

2 回答 2

5

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

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和 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。

于 2021-10-17T16:02:15.443 回答
0

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

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
于 2021-10-17T20:00:48.257 回答