问题标签 [oeis]

我很好奇即使是专业设计的网络也可能具有的限制。特别是这一点是我可以使用的一些见解：

给定：

一组非平凡大小的随机整数（比如至少 500）

一个专业创建/训练的神经网络。

任务：

数字字谜：在给定时间范围内创建无限整数序列的最大表示，其中序列可以以封闭形式表示（即 - n^2、2x+5 等）或在 OEIS 中注册（http: //oeis.org/）。用于创建序列的数字可以以任何顺序从输入集中获取。因此，如果网络被馈入 (3, 5, 1, 7...)，返回 (1, 3, 5, 7 ...) 将是可接受的结果。

据我了解，可以训练 ANN 来寻找特定的序列模式（再次 - n^2、2x+5 等）。我想知道是否可以让它识别更一般的模式，如 n^y 或 xy+z。我的想法是它不能，因为 n^y 可以产生看起来彼此足够不同的序列，以至于无法建立稳定的“基本模式”。也就是说 - 人工神经网络工作方式的本质（获取输入集并对它被训练寻找的静态模式进行模糊匹配）是它们在可以训练寻找的范围方面受到限制.

我做对了吗？

浏览令人敬畏 的整数序列在线百科全书（参见en.wikipedia.org），我偶然发现了以下整数序列：

A031877：非平凡反转数（反转数的整数倍），不包括回文数和 10 的倍数。

通过重用我为回答相关问题“ Prolog 中语言算术的更快实现”而编写的一些代码，我可以毫不费力地写下一个解决方案——感谢clpfd！

我们基于 （之前定义的）定义核心关系 ：a031877_ndigits_/3digits_number/2

核心关系是确定性的，只要 是具体整数，就会普遍终止。N_digit请亲自查看 ! 的前 100 个值N_digit。

让我们运行一些查询！

接下来，让我们找到一些恰好包含四个十进制数字的非平凡反转数：

好的！让我们测量证明上述查询的普遍终止所需的运行时间！

现在，这太长了！

我能做些什么来加快速度？使用不同和/或其他约束？甚至可能是多余的？或者也许识别并消除削减搜索空间大小的对称性？不同的 clp(*) 域（b、q、r、set）呢？还是不同的一致性/传播技术？或者更确切地说是 Prolog 风格的协程？

有想法吗？我要他们所有！提前致谢。

我正在寻找一种半有效的算法，给定一个输入集，从中生成所有总的预序关系（或者，等效地，所有弱序）。您也可以将其称为 n 个标记元素的所有优先安排。

我已经尝试通过首先生成所有大小为 n 的排列然后用“~”折叠这些排列的子序列来实现这一点，但是由于很多重复，这非常低效，而且我也错过了一些结果。大小由 Fubini 数字 1、1、3、13、75、541、4683、47293、545835，...（OEIS 编号 A000670）给出，并且随着 n 快速增长。我只需要前几个，比如说，直到 n=8。

示例：对于 A={a, b, c} 且 n=3，结果是 13 个预购：

b>a>c, b>a~c, b>c>a, b~c>a, c>b>a, c>a~b, c>a>b, a~c>b, a> c>b, a>b~c, a>b>c, a~b>c, a~b~c

我有兴趣计算三角形序列¹，它是对的序列，(i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ... 它遍历所有对(i, j)，限制为i >= j. 具有 i > j 限制的相同序列也很有趣。

(n, n)^{除其他外，这些序列表示从 n 元素集（对于最多2}的序列）中选择 2 个（可能相同）元素的所有方式，或矩阵³的下三角元素的索引。在 OEIS 中，单独的值序列i是A003056，而j单独的是A002262。该序列经常出现在组合算法中，它们的性能可能很关键。

在序列中生成下一个值的一种简单但复杂的方法是：

然而，在计算序列的初始元素时，在检查条件时会出现许多错误预测(i == j)——通常每次i都会增加一个错误预测。随着序列的增加，错误预测的数量变得更少，因为i随着频率的降低而增加，因此j++分支占主导地位并且被很好地预测。尽管如此，某些类型的组合搜索会反复迭代序列中的小项，因此我正在寻找一种无分支方法或其他一些错误预测较少的方法。

对于许多用途，序列的顺序并不那么重要，因此如果可以产生更好的解决方案，则可以允许以与上述不同的顺序生成值。例如，j可以倒计时而不是倒计时：(0, 0), (1, 1), (1, 0), (2, 2), (2, 1), ....

---

¹我也有兴趣知道这个序列的正确名称是什么（也许我为这个问题取了一个更好的标题）。我只是编造了“三角形序列”。

²这里，i >= j版本代表子多集（允许重复），而i > j变体代表正常子集（不重复）。

³在这里，i >= j版本包括主对角线，而i > j变体不包括它。

我正在尝试使用递归定义来实现Hofstadter 的 Q 序列：

我得到了错误的结果n > 3。这是我到目前为止所拥有的：

在线尝试：http: //ideone.com/PmnJRO（编辑：现在有固定、正确的实现）

我认为它不起作用，因为在每次调用Qwhere nis greater than后都会向堆栈添加值2，从而-rot无法按预期工作。

是否有一个简单的调整来完成这项工作？还是我需要使用不同的方法，也许使用变量 for n？

OEIS：A005185

我在 OEIS 中发现了一个感兴趣的序列，我想在 C++ 中为我正在研究的编程竞赛解决方案生成相同的序列。

但是，我在理解序列页面中给出的程序如何工作时遇到了障碍。

这是页面中给出的程序 -

我发现了 PARI 是什么，但我无法将此程序转换为 C++。任何帮助我在 C++ 中生成相同序列的建议将不胜感激。

我尝试使用以下代码片段在 C++ 中生成序列。但我认为我在这两者之间遗漏了某些数字，因为我在在线 IDE 中的一些测试失败了。

我选择了 16、15 和 12 作为限制，否则结果值会溢出长变量类型。

给定一个偶数 (2k) 个元素的列表 L，我正在寻找一种算法来生成具有以下属性的 2k-1 个子列表的列表：

1. 每个子列表恰好包含来自 L 的元素的 k 2-组合（顺序无关紧要的对），
2. 每个子列表只包含 L 中的每个元素一次，并且
3. 所有子列表中所有元素的并集恰好是 L 中所有可能的 2 组合的集合。

例如，如果输入列表是 L = [a, b, c, d]，我们有 k = 2 和 3 个子列表，每个子列表包括 2 对。一个可能的解决方案类似于 [[ab, cd], [ac, bd], [ad, bc]]。如果我们忽略列表中所有元素的排序（将所有列表视为集合），事实证明这也是 k = 2 的唯一解决方案。

我现在的目标不仅是找到一个单一的解决方案，而且是所有可能的解决方案。随着所涉及组合的数量快速增长，最好以巧妙的方式构建所有结果，而不是生成大量候选列表并从中删除不满足给定属性的元素。这样一个朴素的算法可能如下所示：

1. 求 L 的所有 2-组合的集合 C。
2. 求 C 的所有 k 组合的集合 D。
3. 从 D 中选择所有并集等于 L 的集合，称为新集合 D'。
4. 找到 D' 的所有 (2k-1) 组合的集合 E。
5. 从 E 中选择所有集合，联合是集合 C，并让新集合作为最终输出。

这个算法很容易实现，但是对于更大的输入列表来说速度非常慢。那么有没有办法更有效地构建结果列表呢？

---

编辑：这是 L = [a,b,c,d,e,f] 的结果，k = 3，由上述算法计算得出：

满足所有性质：

1. 每个子列表有 k = 3 2-组合，
2. 每个子列表仅包含每个元素一次，并且
3. 一个解决方案的所有 2k-1 = 5 个子列表的并集恰好是 L 的所有可能的 2 组合的集合。

---

编辑 2：根据 user58697 的回答，我使用循环锦标赛调度改进了计算算法：

1. 令 S 为结果集，从一个空集开始，P 为 L 的所有排列的集合。
2. 重复以下操作，直到 P 为空：
   • 从 P 中选择任意排列
   • 为此排列执行完整的 RRT 调度。在每一轮中，来自 L 的元素的排列形成 L 的一个排列。从 P 中移除所有这 2k 个排列。
   • 将生成的计划添加到 S。
3. 如果它们的子列表的并集具有重复元素（即不加起来为 L 的所有 2 组合），则从 S 中删除所有列表。

这个算法比第一个算法性能好得多。我能够将 k = 4 的结果数计算为 960，将 k = 5 的结果数计算为 67200。不过，这个序列似乎没有OEIS 结果的事实让我想知道这些数字是否真的正确，即如果算法正在生成完整的解决方案集。

目前，我可以使用以下蛮力 Prolog 代码枚举有根 平面 未标记二叉树。

注意：请参阅下面的输出列表。

并使用增加的大小输出它们

然而，这是低效的蛮力算法。

是否有更有效的算法来枚举有根平面未标记二叉树？

注意：可以通过使用前两次迭代中的树来生成树，想想斐波那契数，并添加一元分支或二元分支，但这会导致重复树。我自己可以做那个版本，我正在寻找的是一种算法，它第一次以有效的方式生成树而没有重复。

注意：二叉树也称为二叉表达式树或 K <=2 的K-ary 树。

补充

结果

我的 M(15) 的蛮力版本需要 1 小时 27 分钟，而 M(15) 的高效版本大约需要 2 秒。

显然，有效的算法就是这样，效率更高，也是我问这个问题的原因。

莫茨金数

具有根平面未标记二叉树节点的树的数量N由 Motzkin 数给出。参见：OEIS A001006

对于有根平面未标记二叉树，具有 N 个内部节点的树的数量由加泰罗尼亚数给出。有一种更有效的算法可以使用加泰罗尼亚数生成有根平面二叉树。

注意：
基于加泰罗尼亚数字的树数没有一元分支，只计算内部节点。

尽管

基于 Motzkin 数的树数确实具有一元分支并计算所有节点。

请参阅：汤姆戴维斯的
OEIS A000108
加泰罗尼亚语数字

将 Prolog 列表元素与 Motzkin 数相关联

使用低效的蛮力版本的统计信息

参考

Philippe Flajolet 和 Robert Sedgewick 所著的“Analytic Combinatorics”是一本可能有帮助的可免费下载的 pdf 书

另请参阅加泰罗尼亚语标签中的参考资料。

莫茨金数

BNF

使用David Eisenstat 的回答

对我来说，将这些视为笔记或面包屑，以防在我忘记它的几个月后需要再次使用它。

为了测试答案，我使用了安装了 Python 3 的WSL（适用于 Linux 的 Windows 子系统）

motzkin.py使用 Windows 10 我在目录中创建了一个名为

使用 Python 代码

然后在 WSL 中，我创建了一个指向 Windows Prolog 目录的符号链接

并更改为 WSL Prolog 目录

然后开始 Python3

并导入 Python 代码

并以 ubtrees 为 Motzkin 数的参数运行以下命令

并检查 Motzkin 数

退出交互式 Python 使用

重复注释

我了解 Motzkin 数的方法是用笔和纸手动枚举树，并通过使用将一元分支添加到前面的树 M(N-1) 和二进制分支到前面的 M(N -2）树木。

这棵树从 M(4) 棵树中为 M(5) 生成了两次

第一个通过添加一元分支到

其次通过添加一元分支到

完成此操作后，我得到了用于 OEIS 搜索的数字序列 1、2、4、9、21，最上面的结果是Motzkin 数字的A001006。一旦我有了更大的 Motzkin 数字列表，我就使用 Prolog 代码为更大的输入值生成计数，他们都同意了。现在，您可以将 OEIS 添加到您的编程工具箱中，并通过一个有效的示例向其他人演示。

更大的图景

如果你已经读到这里，那么你可能会看到这是一个更大的问题的一部分，它首先在 Prolog 中构建一个系统，可以使用术语重写来解决数学表达式直到基本微积分，但更重要的是显示所采取的步骤。因此，这为生成用作测试用例的二元表达式树提供了一部分方法。下一步是能够单独设置一元和二元节点的数量，而不是让它们由 Motzkin 数固定。我只使用 Motzkin 数字来验证我是否正确生成了组合的子集。现在我有了模式，我可以修改它以接受一个参数用于一元节点的数量，一个用于二进制节点。请参阅：如何使用具有 CLP(FD) 和多个约束的 DCG 枚举组合

只有当我遇到困难时，我才会提出与此相关的问题，所以不要指望看到所有必要的面包屑。

序言输出

我正在研究关于 Jacobsthal 序列 (A001045) 以及如何将它们视为由一些不同的子序列组成的论文。我已经对 A077947 发表了评论，表明了这一点，并包含了一个 python 程序。不幸的是，编写的程序还有很多不足之处，所以我当然想求助于 Stack 看看这里是否有人知道如何改进代码！

这是代码：

我解释这背后的原因如下：

序列A077947由6个数字保根序列拼接而成；根据 Python 代码，这些序列从种子值 af 开始。计算给定 A077947 a(n) 所需的迭代次数约为 n/6。执行时的代码将返回 A077947 的所有值，直到 range(x)，或 A077947 的 ~x*6 项。我发现重复的数字根很有趣，因为我在序列中寻找周期性的数字根保存作为识别数据中模式的方法。例如，在估计需要维护的大型 IT 生态系统（mod7 环境）中警报的真假状态时，数字根保留序列可以对大型数据集进行时间序列分析；这种分析也与预测消费者需求/行为模式有关。采用这些分析方法，将 A077947 雕刻成 6 个数字根保留序列旨在降低复杂性；Python 代码在 6 个“通道”中使用种子值 af 再现 A077947。这一长段归结为声明，“序列项的数字根在模式中重复（1、1、2、5、9、9）。” 更大的说法是，其数字根以某种模式重复的所有序列都可以被分割/分离成相等数量的不同序列，并且这些序列可以独立计算。有一个与这个序列有关的赏金。更大的说法是，其数字根以某种模式重复的所有序列都可以被分割/分离成相等数量的不同序列，并且这些序列可以独立计算。有一个与这个序列有关的赏金。更大的说法是，其数字根以某种模式重复的所有序列都可以被分割/分离成相等数量的不同序列，并且这些序列可以独立计算。有一个与这个序列有关的赏金。

这段代码很难看，但如果不这样编码，我似乎无法得到正确的答案；

由于我似乎无法将重复值正确存储在函数中，因此我还没有弄清楚如何将其编写为函数。

因此，当然，如果这产生了良好的结果，我们希望将讨论与 OEIS 参考文献联系起来。

这是序列的链接： https ://oeis.org/A077947

我需要用 c++ 编写一个 nxn 矩阵，其中 100 <= n <= 1000 和 oeis A072567 序列。这意味着无论我在哪里放置“1”，它都不应该形成一个矩形。其余的地方可以填0

这是包含 105 个对象的 21x21 矩阵