问题标签 [knuth]

Donald Knuth 曾经接到过编写一个计算文件词频的识字程序的任务。

阅读一个文本文件，确定 n 个最常用的单词，并打印出这些单词的排序列表及其频率。

著名的道格麦克罗伊用几行 sh 重写了帕斯卡的 10 页：

作为一个小练习，我将其转换为 Powershell：

我喜欢 Powershell 组合sort | uniq -c成一个Group-Object.

第一行看起来很丑，不知道能不能写得更优雅一点？也许有一种方法可以以某种方式使用正则表达式分隔符加载文件？

缩短代码的一种明显方法是使用别名，但这无助于可读性。

我有一个特定的问题，我想使用Knuth's Algorithm X来解决。但是，我很难将我的问题转化为合适的约束，这些约束构成了算法 X 运行的关联矩阵。

对于我的体育俱乐部夏季锦标赛，我想制定一个时间表，将四名球员组合在一起，而无需在随后的比赛中重新组合任何一对球员。

我认为这可以很好地转化为这样的精确覆盖问题：

• 所有玩家都表示为矩阵的一列
• 每组四名玩家（不管他们的顺序）是矩阵中的一行。
• 因此，当玩家是该组的成员时，将 1 写入矩阵单元格。

在为 20 个玩家设置后，我得到了一个包含 20 列和 4845 行（每个玩家/列 969 行）的关联矩阵。

算法 X 会很好地找到一个解决方案，但这只会涵盖一个（第一）轮。让算法继续下去会为同一轮吐出更多替代解决方案，这对我来说并不感兴趣。所以我围绕算法构建了一个迭代器，它将获取解决方案并根据玩家重叠从关联矩阵中删除行：每当解决方案中的一个组与矩阵的任何行有至少 2 的交集时，该行就会被删除. 在算法第一次运行后，矩阵被剔除到 1280 行。运行算法 X 将找到下一个解决方案，等等，直到它不再存在。

长话短说，这种方法不是精确覆盖问题的正确应用——我必须反复寻找部分解决方案。正确的精确覆盖问题应该包括以某种方式进行的回合顺序。为什么？因为现在我没有探索所有可能的解决方案！20 名球员就是最好的例子。算法 X 将只找到 3 个连续轮次的解决方案。Yet, I do know that there are at least 5, when different intermediate solutions are chosen. 这正是我希望算法 X 能够为我解决的工作。使用上述方法，游戏轮次之间没有回溯。

尽管这个问题足够抽象以至于不需要代码，但这是我在 Python 中实现的 Knuth 的 DLX（带有Dancing Links的算法 X）：

给定玩家列表，此功能将打印中间解决方案到屏幕，直到选项用尽。可悲的是，它没有我希望的那么快，但对我来说这是一个很好的编程练习。:-)

调用dancing_links()上面定义的函数将产生以下输出...

我所期待的更像是……

请注意，它不一定是这个确切的解决方案。这只是我在尝试最终为任意数量的玩家生成时间表时发现的一个示例解决方案。

互联网上有许多不同的指令来进行随机排列，但它们都使用库。有没有办法在不使用任何内置库的情况下进行随机排列？我知道如何使用Math.random(). 生成随机排列是否与Math.random()？洗牌对我来说看起来很复杂。

我的目标是，如果我通过“java randompermutation 3”运行程序，则程序返回 1,2,3 或 1,3,2，或 3,1,2，或 3,2,1，或 2,3 ,1, 或 2,1,3

我正在尝试实现可以​​在 O(n^2) 时间内运行的 Knuth 的最佳二叉搜索树。我有在 O(n^3) 中运行的代码。

M 是成本数组。P 是每个节点的概率。我从以下方面得到一些想法：动态编程：为什么 Knuth 改进了最优二叉搜索树 O(n^2)？. 就我而言，我尝试将第三个循环从 修改for (j = i; j <= i + s - 1; j++)为for (j = root[s+1][i]; j <= root[s][i-1]; j++)。但它不起作用。有人可以给我一些关于这个问题的线索吗？

我对精确覆盖和类似问题相对较新，所以请多多包涵。假设我有一个典型的精确覆盖问题，即。给定一组X和一组X的子集S，我想找到完全覆盖X的S * （ S 的子集）。但是，我希望解决方案S * 恰好包含k 个元素。此外，一种解决方案就足够了。

我知道 Knuth 的算法 X 旨在返回所有可能的解决方案。我应该只运行 Knuth 的算法并遍历解决方案，直到找到具有k个元素的解决方案，还是（我怀疑）有更好的方法？我正在使用 Python 顺便说一句。

对于上下文，X的大小 <100 但S的大小可以是 10^6。k在 <10 时相对较小。

我已经阅读了很多关于“精确覆盖”问题和 Knuth 使用重链表的解决方案的内容。我想我理解了其中的 70%，但仍然对链表“cover”和“uncover”应该如何工作感到困惑。

Knuth 的论文：https ://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf

我理解/已经编码的内容：

• 72 位宽。12 列用于该片的列中具有 1 位的片，然后 60 列 1 和（大部分）0 代表片的形状。所以 72 位宽（作为单个 Python int）乘 1,928 行（每块对每个正方形的每一次有效移动）

• 所有带 0 的节点都已被删除，剩余的链接指针已调整

• 完全链表，每个 Knuth。我的数据结构看起来就像 Knuth 论文第 5 页上的那样：我有常规数据节点、列标题节点、主“h”节点，并且所有内容都是交叉链接的，左/右，上/下等，所以我完成了稀疏矩阵双向链表，左/右和上/下。

• 对于节点，我编写了删除节点并添加回一个节点。

我被困在哪里：

• 当他们说要“覆盖”一个专栏时，我有点困惑。我是否从列标题节点列表中仅删除（取消链接）该列的列标题节点？还是我删除该列中的所有节点？

• 我对行更困惑。当他们说“覆盖一行”时，我不确定要对我的数据结构进行哪些更改。没有像列那样调整“行”标题，我很确定这不是遗漏。没有任何“行标题”，只有列标题。所以如果我想暂时删除一行，我应该改变什么？我是否循环遍历该行中的所有节点并将它们全部删除？如果我回溯，然后将它们全部添加回来？似乎有很多要删除和添加的内容，所以我很确定这是我不理解的部分。

很高兴回答/编辑以使问题更清楚。由于我的代码很长而且很乱，我现在不打算发布它（除非人们真的认为它会有所帮助，但它是链表，就像 Knuth 展示的那样，所以我认为代码会分散注意力。

那么，在使用 Knuth 的链表（带有列标题）时，如何“覆盖”一列，更重要的是，如何“覆盖”一个 ROW？

谢谢，马克

我正在关注使用 Knuth 的“Dancing Links”DLX 算法解决简单“精确封面”问题的 Wikipedia 示例 - 示例在这里：https ://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example

在最后一步，他们显示了简化的矩阵：

他们说这是一个失败的解决方案，但我们到底是怎么知道的呢？是不是只有一行，任何一行？还是最左边的列有 0 而右边的 3 列有 1？或者也许它下降到 1 行并且该行不是完全 1 的？

真的试图理解所有这些东西（最终与 Pentominoes 一起使用，即使我可以从网上下载解决方案，但我想自己编写代码以供娱乐和学习）

任何人都可以阐明在这里使用不同值的影响吗？

CLR System.Random (random.cs, 61) 似乎引用了使用的算法

并使用这行代码 (random.cs, 80)

但是，查看正在使用的明显算法（C 中的数字食谱，283）

(Knuth 124) 谈到随机数生成曲线下的分布区域被分成 31 个矩形。

我不是数学天才，试图遵循这个算法会让我的大脑有点受伤。

随机的.cs。Microsoft 参考源，.NET Framework 4.8 https://referencesource.microsoft.com/#mscorlib/system/random.cs

出版社，Teukolsky 等。等，C 中的数值食谱：科学计算的艺术，第 2 版。 https://www.cec.uchile.cl/cinetica/pcordero/MC_libros/NumericalRecipesinC.pdf

Donald Knuth，计算机编程的艺术，第三版，第一卷。2 半数值算法 https://seriouscomputerist.atariverse.com/media/pdf/book/Art%20of%20Computer%20Programming%20-%20Volume%202%20(Seminumerical%20Algorithms).pdf

该算法保证以均匀随机顺序重新排列元素。均匀随机是什么意思？

我正在尝试在 C 中实现 Knuth 的拓扑排序算法。当我搜索在线资源时，我看到的只是 Kahn 算法的实现，这让我很困惑。他们都一样吗？还是他们不同？这是我根据我研究过的实现。

样本输入：

输出：

预期输出（来自我们的课堂活动）：

我的代码接受对输入并在应用拓扑排序后返回顺序。为简单起见，我假设该条目是拓扑排序的有效图。