1

我想有效地生成所有长度为N的单词（N 是素数），不包括同构单词。

如果具有N个元素的有限循环群存在将单词 A 转换为单词 B 的自同构，则单词A与单词B同构。

设V - 是K个元素的字母表。

例如V = {a,b}

设N为 7

那么，例如单词 A = {a,a,a,b,b,a,a} 与单词 B = {a,b,a,a,a,a,b} 和单词 C= { a,a,b,a,a,b,a} 因为有限循环群 S= {0, 1, 2, 3, 4, 5, 6} 具有自同构 {0, 4, 1, 5, 2, 6, 3} 和 {0, 5, 3, 1, 6, 4, 2}

最简单的算法是

  • 找到所有可能的词
  • 找到具有 N 个元素（N 素数）的有限循环群的所有自同构
  • 排除同构词

不幸的是，这种方式在算法上效率不高。

4

1 回答 1

0

如果您对简单算法的反对是需要存储所有独特的单词，那是没有必要的。对于每个 K^N 单词，测试它在字典上是否小于或等于其所有同构（规范），如果是，则返回它。

我们可以做得更好

  • 生成所有规范 (N−1) 字母后缀并附加每个可能的首字母。

  • 通过在可能的字母中迭代第二个位置并生成其他字母不小于第二个位置的后缀来生成 (N-1) 个字母后缀，然后再进行上述的规范性测试。

我们可以走得更远，但我怀疑增加的复杂性是否会收回成本。

于 2021-07-14T01:08:53.567 回答