问题标签 [heaps-algorithm]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
2 回答
2187 浏览

javascript - 创建一个由 JavaScript 中的数字 1-9 组成的所有唯一 4 位数字的数组

我的任务是创建一个由所有排列/给定数字数组的 4 位数字组成的数组:[1,2,3,4,5,6,7,8,9]。不能有重复的数字,因为每个值必须是唯一的。以下是我的解决方案,但我正在努力将递归应用于该过程。我希望它具有适应性,因此如果条件发生变化,即函数必须生成 5 位数字甚至 6 位数字的所有组合,因为需要更改的代码很少,并且添加递归可以轻松实现这一点。正如您在下面看到的,代码确实可以工作,但如果条件改变,这将需要更多的嵌套 for 循环。我正在寻找递归解决方案。这似乎不是一个好的解决方案,但任何建议将不胜感激。我在网上看到很多关于创建 4P4 或 5P5 但不是 9P5 样式的解决方案。我试图应用堆的算法但没有成功。

0 投票
0 回答
45 浏览

javascript - 堆排列算法以相反的方式完成......?

我试图通过在数组的开头而不是最后一个固定元素来以相反的方式使用堆算法。但我无法得到结果。虽然我理解了这个算法的理论部分,但当我尝试实现它时却很困惑。我主要对 if 条件中的交换语句感到困惑。(请检查评论)。如果有人能说出问题所在,那将很有帮助。谢谢你的时间。

0 投票
1 回答
1662 浏览

c - 从 C 中的 n 生成 k 个排列

我基本上需要 C 中以下 Pythonitertools命令的等效结果:

a = itertools.permutations(range(4),2))

目前,我的过程涉及首先从 10 个元素中“选择”5 个元素,然后为这 5 个元素生成排列,如下所示

这种方法的问题是输出的顺序。我需要它是(a),而我得到的是(b),如下所示。

我正在使用的另一种方法如下

记忆是我的限制,所以我不能无限期地存储排列。性能需要比上面的算法好,当n是 50 和k10 时,我最终会迭代更多无效组合(60+%)

我知道Heap用于在适当位置生成排列的算法,但它再次为整个数组生成,而不是像我需要的那样为 n 的 k 生成。

问题。

  1. 有没有比迭代 n^k 次更好的方法呢?
  2. 我可以制作一个惰性迭代器,在给定当前排列的情况下移动到下一个排列吗?

编辑这不是 std::next_permutation 实现的副本,因为它将置换整个输入范围。我已经明确提到我需要 n 个排列中的 k 个。即,如果我的范围是 10,我希望长度 (k) 的所有排列都说 5,当长度或排列与输入范围的长度相同时,std::next_permutation 起作用

更新 这是一个丑陋的递归 NextPerm 解决方案,它比我的旧解决方案快 4 倍,并且像 Python 惰性迭代器一样提供增量 nextPerm。

0 投票
2 回答
214 浏览

arrays - x位置中n个字符的置换算法

例如 {&, *, %} 的置换算法被放置在 8 个位置:

  1. &&&&&&&&&
  2. &&&&&&&&*
  3. &&&&&&&&%
  4. &&&&&&&*%
  5. &&&&&&&**

...

我在网上看到的堆的排列算法只适用于字符数等于位置数的那些,而那些可以使用不等字符数和位置数的那些,仅适用于整数,而不适用于字符。我还不得不说到目前为止我还没有达到任何工作算法,因为我对算法一无所知。我试了一次,看到堆的算法后,我无法命名它的算法!如果有帮助:

  1. 添加&到输出数组。
  2. 添加%到新索引上的输出数组。
  3. 添加*到新索引上的输出数组。
  4. 对每三个做一个递归算法。

但我显然无法处理数组索引。我也尝试使用从 0 到 2 的数字来表示 &、%、*; 但我没有得到一个好的答案。

0 投票
1 回答
136 浏览

javascript - 堆的算法返回数组而不是打印

我试图让这个堆算法返回一个排列数组,而不是如下打印。我知道这可以通过在函数外部声明一个数组并推送到它来完成,但是我想避免这种方法。如何在不使用外部数组的情况下使其返回排列数组?

0 投票
2 回答
333 浏览

swift - 快速堆算法

我在 Swift 中有一个堆算法的实现,我试图将其转换为不使用 inout 参数。

但是我得到了不同的结果(第二个是错误的,提供了重复的排列)。出了什么问题,我该如何解决?

原始实现:

输出:ABC BAC CAB ACB BCA CBA

没有 inout 参数的实现:

输出:

输出:ABC BAC CBA BCA ABC BAC

请注意,我们在此输出中没有得到 CAB,并且还重复了“BAC”和“ABC”。

我不太明白这两者是如何不等价的,并且想创建一个没有 inout 参数的算法版本。

0 投票
1 回答
227 浏览

python - 堆算法产生相同的排列两次

我目前正在用 Python 实现 Heaps 的算法,但我目前的解决方案是两次返回一些排列。

此代码产生以下结果:

由于我不想要重复的结果,

我究竟做错了什么?

0 投票
1 回答
187 浏览

python - Heap's algorithm with permutation signature

I am making a code that can generate all the permutation of a list of elements and the signature of the permutation based on the original list.

In general the number of permutations is given by the Stirling numbers of the first kind as a composition of k = n - C-cycles that partition the n elements.

The number of ways to partition n elements into k cycles is to partition n - 1 non-maximum element into k cycles and splice in the maximum element in one of n - 1 way or put the maximum element in its own cycle and partition the n - 1 non-maximum element into k - 1 cycles. Then, the sign will be given by (-1)^N-C where N is the number of indexes and C is the number of cycles formed when an element is moved from their original position.

I have coded a variation of the Heap's algorithm which can produce the signature of each permutation.

In the routine permute the list a is introduced the first member of the list a[0] is the sign which in this case is +1 and for each permutation, the sing of the list is multiply by -1. So far I think the code works, this is the result for the test.

My questions are: Do you think my code will be applicable to any list size, i.e. [1,A,B,C......,Z_n]? Is there a more efficient way to generate the permutations and their signs?

0 投票
1 回答
293 浏览

javascript - 堆的算法 - JavaScript

我对堆算法的工作原理有一个很好的理解,但我不知道如何将每个唯一的排列添加到数组中并根据算法的递归性质返回它。

为什么它只添加相同的排列,但控制台日志打印出不同的排列?

0 投票
1 回答
193 浏览

java - 如何将所有数组排列迭代地返回到二维数组中?

我正在尝试编写一个程序,它将遍历字符串数组的所有可能排列,并返回一个包含所有排列的二维数组。具体来说,我正在尝试使用长度为 4 的 String 数组来返回具有 24 行和 4 列的二维数组。

我只找到了迭代打印字符串但没有在数组中使用它们的方法。我也找到了递归方法,但是它们不起作用,因为我正在与其他人一起使用此代码,并且递归函数要困难得多。

对于我想要代码执行的操作,我知道标题应该是:

//我尝试使用带有堆算法的递归方法,但它的参数非常//复杂。

我对编程很陌生,任何帮助将不胜感激。