问题标签 [heaps-algorithm]

我需要证明堆算法生成排列的正确性。它的伪代码如下：

（摘自 Levitin 的算法设计与分析简介）

我知道我需要使用归纳法来证明它的正确性，但我不确定该怎么做。我已经证明了数学方程式，但从未证明过算法。

我在想证明会看起来像这样......

我只是不确定如何完成感应步骤。我什至在正确的轨道上吗？任何帮助将不胜感激。

Heap 的算法是一种系统的方法，可以循环遍历 N 个元素的所有排列“一次交换一次”。对于奇数 N，它特别简洁，因为最终排列似乎只是与第一个排列不同的一次交换。

但是，即使是 N，这种环绕也不会发生。例如，对于 N=4，排列顺序为：

那么，有没有人有一个交换算法可以环绕 N 呢？如果不是，那么仅 N=4 怎么样？

我一直致力于实现堆算法的递归版本。这是伪代码的链接：http ://en.wikipedia.org/wiki/Heap%27s_algorithm

在我进入递归部分之前，一切都很顺利。我知道我还没有放入交换元素，但我还没有走到那一步。运行失败而没有显示错误，直到我使用 gcc 调试器告诉我存在分段错误。这是我的代码：

我正在尝试在 C++ 中实现堆的算法。
但是，如果它正在置换的字符串的长度为 4，则该算法开始重复。代码如下：

这是输出。它在第 13 行重复

谢谢你们，欢迎任何帮助！

试图重现堆的算法，以生成整数数组的所有可能排列，但我无法解决除三个以外的其他整数。来自维基百科的堆算法：

我的代码：

我在做什么错和误解？为什么它仅适用于 [1,2,3] (n=3) 作为输入，而不适用于 n=2 或 n=4？

运行：

感谢您的回复，但这不是问题。在我问这个问题之前，我尝试改变它，但是如果我正确理解了 Wiki 页面，我认为从 1 开始是算法的一部分，因为它明确说明（即使没有提到特定的语言/for-loop-scheme）。下面是 n=4 的输出，其中包含多个重复项。链接到 Wiki 页面：http ://en.wikipedia.org/wiki/Heap%27s_algorithm

I have spent the whole day (finally) wrapping my head around a permutation algorithm in practice for an admissions application on Friday. Heap's algorithm seemed most simple and elegant to me.

here is an example of it: http://en.wikipedia.org/wiki/Heap%27s_algorithm

The log for the final permutations array is here:

It gets the first 12 permutations alright, and then a ',' gets added mysteriously, and the first 12 permutations are repeated. I'm stumped.

EDIT: above is the updated code taking into consideration what comments said to help. Still only getting half the permutations.

我正在尝试在 C++中实现堆的算法。我觉得我已经完全按照算法的工作原理编写了代码，但它给出了错误的结果。

我一直在努力完成这项工作。对于上面代码中的向量，它给出了荒谬的结果：

123 123 123 123 213 213 321 321 321 231 231 123 123 123 213 213

我需要迭代整数元组的排列。必须通过在每一步交换一对元素来生成订单。

我找到了有关 Heap 算法的 Wikipedia 文章（http://en.wikipedia.org/wiki/Heap%27s_algorithm），它应该可以做到这一点。伪代码是：

我试图在 python 中为此编写一个生成器：

这会按以下顺序产生排列（对于 [0,1,2,3] 的输入）：

这似乎很好，直到最后一步，这不是一对交换。

我究竟做错了什么？

我已经实现了堆的算法来查找数组 A 的元素的所有排列：

我是 Java 新手。问题是我想让 B 作为函数 perms(A) 的输出（返回），但是在这个实现中，我必须初始化一个 int[n! + 1][A.length] 调用函数之前的 B 数组。我该怎么做？
java中是否有类似私有变量或任何东西来帮助递归函数记住以前调用中的变量？

谢谢

我试图用 C# 编写堆算法的实现，但它不能正常工作。我正在尝试创建一个通用实现，它将找到字符串的所有排列，并将它们添加到列表中。

我是这样开始的：

这是我的实现：

该算法确实产生了正确数量的排列（在本例中为六个），但排列本身是不正确的：

我不认为我偏离了Wikipedia 上 Heap 算法的伪代码示例，而且由于该算法的递归性质（概念化非常棘手），我很难对此进行调试。

任何人都可以提供有关问题可能是什么的任何见解吗？

^{PS 不是作业，只是为了好玩。}