问题标签 [knuth]

如果我的问题听起来很愚蠢，我很抱歉，因为我对数据结构的理解不是很好。

我一直在阅读Knuth 的 Dancing Links算法，并且非常了解它的基本工作原理。提到dancing link的数据结构可视化看起来像一个有列有行的表格，每个单元格都连接到它们的上、下、左、右单元格。我还读过这个算法中使用了循环双链表。

我想知道的是如何将双链表精确地制成具有列和行的表？

据我所知，大多数双链表只有 2 个指针（上和下），这是否意味着我必须制作自己的自定义链表，它有 4 个指针（上、下、左和右）？还是有其他方法？

提前致谢。

我必须在 python 中使用元素之间的最小比较次数来对排序 5 个元素的列表的执行计划进行建模。除此之外，复杂性无关紧要。

结果是一个对列表，表示在另一个时间对列表进行排序所需的比较。

我知道有一种算法可以在 7 次比较中做到这一点（元素之间，总是，而不是复杂性），但我找不到可读的（对我来说）版本。

如何对 7 个比较中的 5 个元素进行排序，并为排序构建“执行计划”？

PD：不是作业。

I have created a random number generator using gettimeofday() function, in C. Now,I need to evaluate this using statistical or empirical methods developed by Knuth. I searched exhaustively for the same, but could not find a workable solution. Or I may be wrong. Please help me in evaluating this RNG according to the above standards.

我有一个 C++ 任务，我必须用我选择的容器设计一个简单的 Knuth 问题解决方案，并研究生成的性能数据。请参阅下面的问题：

从纽约到加利福尼亚，三百万名不同的人被端对端放置。每个参与者都得到一张纸条，他在纸条上写下自己的名字和排在他西边的人的名字。队伍最西端的那个人不知道该怎么办，所以他把纸扔了；剩下的 2,999,999 张纸条被放在一个巨大的篮子里，并被带到华盛顿特区的国家档案馆。篮子里的东西被完全打乱并转移到磁带上。

此时，一位信息科学家观察到磁带上有足够的信息可以按照原始顺序重建人员列表。一位计算机科学家发现了一种方法，可以通过少于 1000 次的数据磁带进行重建，只使用磁带的顺序访问和少量的随机存取存储器。这怎么可能？

[换句话说，给定 1 ≤ i < N 的对 (xi, xi+1)，以随机顺序，其中 xi 不同，如何获得序列 x1 x2….xN，将所有操作限制为串行技术，适用于磁带上。当没有简单的方法来判断两个给定键中的哪一个在另一个之前时，这就是排序问题。

根据我的研究，我决定使用 unordered_map，而不是列表或法线贴图。我不明白的是已经提供给我们以实现为代码的幼稚解决方案：

将论文视为 (Name, Name) 元组的集合，后继者（西边邻居）和前身（东边邻居）都可以从这些元组中建立。

我的第一个问题 - xc 只是一个随机元素，因为容器的性质无法确定顺序吗？

我的第二个问题 - 我们得到的名字在一个文件中，如下所示：

那么天真的解决方案是说我应该取名字并将其放入一个列表中，然后将姓氏放入另一个列表中吗？

抱歉，如果我完全离开，但我真的试图理解这一点！

感谢您提前查看此问题。

我正在尝试订购以下物品清单：

变成如下顺序：

这是通过以下方式完成的：

1. 取第一对并将名称放入列表
2. 使用对的第二个名称，找到它用作名字的对
3. 将该对的第二个名称添加到列表中
4. 重复 2 & 3

我正在用这些对填充 unordered_map，然后对每个名称进行排序并将其添加到列表中。这可以在以下代码中看到：

注意：我不确定此时“push_front”是否正确，因为我只插入了第一个值。

我的问题是有人可以给我一些关于如何解决这个问题的见解吗？因为我不确定最好的方法以及我的想法是否正确。任何见解将不胜感激。

我的教授解决了kmp故障功能如下：

从网上查到的其他文字，我发现可能是错的，我又回去跟他确认，他告诉我他完全正确。有人可以通过简单的逐步方式向我解释为什么他认为这是对还是错？谢谢

我正在尝试将 knuthBendix 应用于大量重写规则。因此，我尝试让它在不同的集合上并行工作。

例如，我尝试运行：

我使用编译ghc -threaded并通过执行+RTS -N。如果我并行运行其他算法，它会起作用。但对于 knuthBendix，它没有。

有人知道解决方案吗？

谢谢，弗兰兹

最近，我读到了一些关于 Ackermann 函数和 Knuth 的向上箭头符号的内容。我知道符号用于表示变化很大的数字。但是，我找不到这种表示法的任何实际用途 - 该表示法应用于某些算法或程序中。那么有谁知道这个符号在现实世界中有什么用途吗？

我正在使用 knuth shuffle 来随机化一个数组。我希望能够添加另一个数组并以相同的方式随机化。我之前曾想过将数组分隔在字符串中，例如['A|1|I,B|2|II,C|3|III,D|4|IV']等。

在stackoverflow上，我读到了这个，但我不知道如何安排它进行knuth shuffle。

这是我目前用来从第一个数组中获取字符串的 JS，附加代码取自上面的链接。

我正在尝试在 java 中实现 Knuths Mastermind 算法。该算法在本文中进行了解释，论文。到目前为止，这就是我实现它的方式，但它比算法应该花费的最多 5 次猜测要多。

假设其他方法，例如评分方法和 getMax 方法，按预期工作，为什么这不起作用？