问题标签 [heaps-algorithm]

我正在研究递归算法的时间复杂度，我想知道生成 n 个对象的所有可能排列的堆算法的复杂度。

我认为它的时间复杂度是 O(n * n!) 但我不确定。所有的帮助将不胜感激。谢谢你。

我一直在阅读像Steinhaus-Johnson-Trotter和Heap这样的算法来生成排列，包括 Sedgewick 关于该主题的论文。但是，当所有元素都不同时，这些似乎都有效。如果我有可以共享值的元素，并且我想过滤掉N!观察性重复的详尽排列部分，会发生什么？

我听说过字典法。C++ 库中甚至还有两个与它们相关的函数。但是如果数据是无序的呢？也就是说，我只有一个等价谓词，而不是排序谓词。

Sedgewick 研究的那些算法是否可以适应跳过等效排列（当然，第一个除外）？

有一个现有的查询“<a href="https://stackoverflow.com/q/30963085/1010226">distinct permutations of a list with repeats”可能很接近，但它的问题和解决方案集在 R ，而不是一般的。

我正在尝试在 Java 中实现“堆算法”（wiki），它构造了给定集合的所有排列。（我知道这在技术上不是 Heap 的算法，因为这里指出了一些微妙之处，但这对我来说目前并不是非常重要）。

我所拥有的：我从一段有效的代码开始，做我想做的事：

再说一遍：这段代码可以正常工作并输出我想要的东西。

良好的输出：

我想要什么：我想复制上面的代码，但是用Lists（或ArrayLists、LinkedLists 等）替换所有数组实例。

我尝试过的：这是我尝试过的修改：

但是，与第一个代码块不同，这并没有给出我想要的：

错误输出：

第二个代码块中发生了什么使其不正确？我 100% 确定这是由于我对ListJava 中 s 的一些微妙之处缺乏了解，但我不知道罪魁祸首是什么。

在问这里之前，我尝试了不添加的第二个代码块List<T> aTemp = new ArrayList<T>(a);，并且我还尝试修改它的各个部分以更改 to 的实例，a反之亦然aTemp。我试过的都没有用。

编辑 1

在下面的评论中，用户@GPI 在我的情况下指出了一个错字。更正T temp = aTemp.get(0);后T temp = aTemp.get(i);，我有以下输出：

请注意，这也是不正确的，因为它包含许多实际上不是排列的重复项/列表（例如[d, d, d, c]）。

给定一个值列表，例如vec![0, 0, 1, 2]，我想创建一个迭代器来生成其所有唯一排列。那是，

（请注意，有 12 种不同的排列，而如果我们有 4 个不同的元素，则将有 24 种不同的排列）。

已经有一种方法可以使用itertools 包生成排列（以及其他迭代器，如组合或没有替换的组合），但是对于排列，没有办法将排列限制为唯一的排列。

有一种相当有效的算法可以生成通常称为堆算法的排列，但是这没有考虑值的相等性/重复性。

这个问题在使用生成器的语言（例如 Python ）中实现并不太棘手，但我觉得这在 Rust 中更棘手（至少与上面的解决方案相比），因为它需要使用迭代器（必须保持内部状态） ，或使用生成器（目前不稳定）。

我的代码的目标：尝试创建一个数组的 ArrayList，其中包含传递的数组“p”的所有排列。

方法：使用Heap 的算法，尝试生成所有排列，每个排列 bieng 存储在 ArrayList 中，使用 add() 方法。

问题代码进入： ArrayList 中的所有元素都更新为相同的值（找到的最新排列）。

代码：

O/P 代码：

期望的 O/P：列表应该包含在每次迭代中添加的不同排列。（在这种情况下，存在 6 个这样的排列。）

如果我删除了数组列表，并且只是简单地使用打印来获取排列，则排列都是由这段代码正确生成的......

问题/查询：

• 请告诉为什么会发生这种情况，就好像我选择在每个 if(size==1) 条件下直接打印数组'p'，然后 o/p 是正确的，只有 ArrayList 实现会产生问题......
• 有什么办法解决这个问题？（最好是最有效的修复）。

我正在尝试在 python 中实现 Heap 的算法，但是在重复一些解决方案时遇到了麻烦。我对错误所在的位置感到困惑。这是实现：

对于输入[0, 1, 2]and 3，我得到：

最后 2 个结果，从第一个和第二个重复，缺少：

我搜索了多个地方并尝试了该算法的不同实现，但无论我尝试多少次，我似乎都无法让它发挥作用。我错过了什么？

我需要n在蛮力算法中获得长度可迭代的所有排列。我不想使用itertools或任何其他外部包。

我想我可以使用堆的算法，但我的代码只返回一个重复 n 的排列！次：

我不明白为什么会这样。我还试图弄清楚是否有更有效的方法来做到这一点，也许是使用递归函数。

例如，我有这组k=5元素[1,2,3,4,5]，我想要长度的所有排列n=2。

问题是我不能使用 STL、外部数学库等。

我尝试的是使用堆算法生成所有元素的所有排列，然后包含所有 k 排列的前 n 个数字中的 n 个元素的所有排列，我可以截断和删除重复项，但是复杂性是方式太高（n！）

我知道这个问题有一个很好的解决方案，因为我已经看到在有关置换字符串的问题中使用额外的模块/库来完成此操作。

额外信息：我只需要这个来暴力破解一个不平衡的分配问题，当我被允许“暴力破解”这个问题时，匈牙利算法似乎太长了。我的方法没有接近允许的执行时间，因为当我有一个例如大小为 8x3 的数组时，我的算法需要 8 个！当它肯定可以优化到更小的数字时进行比较。

我正在处理 CodeWars.com 上的一些“Kata”，并被困在 Permutations 问题上。

这是问题所在：在这个 kata 中，您必须创建输入字符串的所有排列并删除重复项（如果存在）。这意味着，您必须以所有可能的顺序对输入中的所有字母进行洗牌。

例子：

排列的顺序无关紧要。

这是我的解决方案：

当你传入一个字母时，它工作正常。两个字母，它返回undefined。我已经使用 return 控制台记录了 if 语句块，它应该返回正确的答案，但结果仍然是undefined. 考虑到它在 if 语句中得到了正确的答案并且没有进入 else 块，我不知道为什么这不起作用。

先感谢您！

我是编程新手。我正在研究堆算法，特别是非递归方法。互联网上没有太多关于算法如何工作的解释。我从Bernardo Sulzbach那里找到了这篇作品，但他没有解释他的算法是如何工作的。几天来我一直坚持下去，尝试了一切都无法弄清楚。我在每一行之后添加了注释以使自己理解 - 这里发生了什么？但我仍然无法让它工作。难道我做错了什么？请帮忙。