求全排列一共有四种方法,字典序法,递增进位制数法,递减进位制数法,邻位对换法.我在这里讲最简单的字典序法.
这个生成法要求传进来的序列必须已经按从小到大人规律排过序.否则它不能生成正确的全排列.至于为什么用这个方法就可以生成全排列,我的知识有限,证明不了,只有拿来用了再说.
假定序列为a1,a2.... an (n > 0) ,如123456789,它从123456789开始,一直到987654321结束,中间有n个值,寻找这n个值需要做n步下面的操作:
1.找出比右边数字小的第一个数 找到这个数后,把它的位置记下来.设这个位置为pos_left;如果找不到,就说明排列完成了.
2.从右到左寻找第一个大于pos_left所在值的数,设为pos_right.
3.交换a[pos_left]与a[pos_right]的值.
4.逆转a[pos_left+1]到a[n]之间的值.
到此,寻找一个排列的步骤完成.
来个例子吧, 123, 做第1步,找到2比3小.pos_left = 2. 再做第2步,找到3比2大. pos_right = 3.然后做第3步,交换,得到 132 , 又因为pos_left后只有一个数,所以不用做逆转了.
这个太短了,干脆来个长点的 124653, 第1步找到4, pos_left = 3, 第2步找到5, pos_right = 5.然后交换得到125643, 再逆转得到125346, 从而得到新的排列.然后再对这个排列做上面4步,求出下一个排列....直到最后最后没有新排列可求出来.
java 代码
- public class Permulation {
-
-
-
-
- public static void main(String[] args) {
- int[] arr = { 1, 2, 3, 4 };
- do {
- for (int i = 0; i < arr.length; i++) {
- System.out.print(arr[i] + ",");
- }
- System.out.println();
- } while (new Permulation().nextPermutation(arr));
-
- }
-
- public boolean nextPermutation(int[] arr) {
- int postLeft = -1;
- for (int i = arr.length - 1; i > 0; i--) {
- if (arr[i - 1] < arr[i]) {
- postLeft = i - 1;
- break;
- }
- }
- if (postLeft < 0) {
- return false;
- }
-
- int postRight = -1;
- for (int i = arr.length - 1; i >= postLeft; i--) {
- if (arr[i] > arr[postLeft]) {
- postRight = i;
- break;
- }
- }
- swap(arr, postLeft, postRight);
- reverse(arr, postLeft + 1, arr.length);
- return true;
- }
-
- public void swap(int[] arr, int ind1, int ind2) {
- int t = arr[ind1];
- arr[ind1] = arr[ind2];
- arr[ind2] = t;
- }
-
- public void reverse(int[] arr, int ind1, int ind2) {
- for (int i = 0; i < (ind2 - ind1) / 2; i++) {
- swap(arr, ind1 + i, ind2 - 1 - (i));
- }
- }
- }
分享到:
相关推荐
非递归算法的优点在于它可以避免深度过大的调用栈,从而在处理大型数据集时减少内存消耗。这里以1到6的数字为例,我们可以构建一个迭代的解决方案来生成全排列。首先,我们需要一个容器,例如数组或列表,来存储当前...
在提供的文件名称“新建 文本文档.cpp”中,我们可以推测这是一个C++语言的源代码文件,它很可能包含了实现全排列非递归算法的代码。C++是一种强大的面向对象编程语言,非常适合处理这种需要高效计算的问题。 ...
总之,全排列的递归算法是C语言编程中一种重要的算法实现,通过理解递归思想和巧妙地处理数组元素,我们可以有效地解决这类问题。同时,掌握这一算法也对理解和解决更复杂的算法问题有着积极的帮助。
此外,还可以使用非递归的迭代方法,如“回溯栈”来实现全排列。这种方式避免了递归带来的栈空间消耗,但实现起来相对复杂,需要手动维护待处理的元素集合和当前排列状态。 总结,全排列算法主要通过递归或迭代实现...
在C++中,我们可以使用非递归和递归两种方法实现全排列算法。 ### 非递归全排列算法 非递归实现的核心思想是通过不断调整已排序的序列,找到下一个更大的排列。算法主要分为以下几步: 1. 找到当前排列中的最小...
其中可能包含了代码示例,讲解了如何使用数组来存储和生成全排列,也可能讨论了算法的时间复杂度和空间复杂度。 另一份文件“c4.txt”可能是一个测试案例或结果输出,包含了一些特定的n=4的全排列示例,用于验证...
在C语言中,可以使用递归或非递归方式实现。递归版本通常从第一个元素开始,对于每个位置,尝试将剩余元素中的每一个放在该位置,并递归地生成后续的排列。非递归版本则利用栈或者队列来存储当前状态,逐步推进排列...
下面是一个简单的全排列递归算法实现(用伪代码表示): ```python function permute(data, start, end): if start == end: // 基本情况:只有一个元素 print(data) else: for i in range(start, end + 1): // ...
在编程领域,全排列是一个经典的算法问题,它涉及到数组或字符串的所有可能的顺序组合。...在学习和实践过程中,你还可以尝试优化算法,例如使用迭代而非递归,或者采用更高效的回溯策略,以提高性能。
* 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 * 二叉查找树-两数之和 * 二叉查找树-中第K小的元素 * 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从有序链表构造平衡的二叉查找...
对于大型数据集,递归可能会导致栈溢出问题,因此有时会考虑非递归的迭代方法,如回溯搜索或者使用堆栈来存储中间状态,以提高效率。在实际应用中,可以根据具体需求和性能要求选择合适的算法实现。
在实际应用中,可以考虑使用其他数据结构,如堆栈或队列,或者采用非递归的方法来优化性能。 总的来说,Python中实现数组全排列的方法展示了递归在解决组合问题中的强大能力。通过理解递归的工作原理和全排列的概念...
包括数组全排列的两种主要方法:逐个追加组合法与递归法;并讲解字符串相关操作以及各种特定整型数组问题,例如求下一个非重复数等,并针对某些特定问题提供了不同场景下的性能优化方式。 适合人群:具有C++基础并对...
### Python非递归全排列实现方法详解 #### 一、引言 在计算机科学与编程领域,全排列问题是一个常见的组合数学问题。全排列是指从给定的n个不同元素中取出m(m≤n)个元素,按照一定的顺序排列起来的方式。递归...
5. **优化和变种**:如使用迭代而非递归,或者在特定条件下提前剪枝以减少计算量。 在实际应用中,全排列算法常用于密码学、组合优化、搜索问题等领域。通过这个课程设计,学生不仅能掌握全排列的实现,还能提升...
总结来说,MATLAB中的全排列矩阵生成是一个涉及组合优化、递归和非递归算法的问题。通过学习和实践提供的程序,你可以掌握如何在MATLAB环境中高效地生成全排列,这对于提升编程技能和解决相关问题具有重要意义。
解决全排列问题可以使用递归算法或非递归算法。递归算法通常基于分治法的思想,通过逐个交换字符来生成新的排列,保证不遗漏任何排列的关键在于递归前保持序列的顺序。而非递归算法则涉及到从字典序最小的排列到字典...
在Java中,我们可以使用递归或者字典序的方法来实现全排列算法。 首先,让我们深入理解递归方法。递归是一种解决问题的方法,它将问题分解成更小的子问题,直到子问题变得足够简单可以直接解决。在全排列问题中,...
局部搜索是一种优化技术,常用于解决复杂问题,如在大量可能解中寻找最优解。在这个实验报告中,局部搜索被应用于...改进方法可能包括非递归算法、动态规划或使用数据结构优化存储和比较过程,以提高效率和避免重复。