`

求数组的全排列的非递归算法

阅读更多
求全排列一共有四种方法,字典序法,递增进位制数法,递减进位制数法,邻位对换法.我在这里讲最简单的字典序法.
这个生成法要求传进来的序列必须已经按从小到大人规律排过序.否则它不能生成正确的全排列.至于为什么用这个方法就可以生成全排列,我的知识有限,证明不了,只有拿来用了再说.
假定序列为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 代码
 
  1. public class Permulation {  
  2.   
  3.     /** 
  4.      * @param args 
  5.      */  
  6.     public static void main(String[] args) {  
  7.         int[] arr = { 1234 };  
  8.         do {  
  9.             for (int i = 0; i < arr.length; i++) {  
  10.                 System.out.print(arr[i] + ",");  
  11.             }  
  12.             System.out.println();  
  13.         } while (new Permulation().nextPermutation(arr));  
  14.   
  15.     }  
  16.   
  17.     public boolean nextPermutation(int[] arr) {  
  18.         int postLeft = -1;  
  19.         for (int i = arr.length - 1; i > 0; i--) {  
  20.             if (arr[i - 1] < arr[i]) {  
  21.                 postLeft = i - 1;  
  22.                 break;  
  23.             }  
  24.         }  
  25.         if (postLeft < 0) {  
  26.             return false;  
  27.         }  
  28.   
  29.         int postRight = -1;  
  30.         for (int i = arr.length - 1; i >= postLeft; i--) {  
  31.             if (arr[i] > arr[postLeft]) {  
  32.                 postRight = i;  
  33.                 break;  
  34.             }  
  35.         }  
  36.         swap(arr, postLeft, postRight);  
  37.         reverse(arr, postLeft + 1, arr.length);  
  38.         return true;  
  39.     }  
  40.   
  41.     public void swap(int[] arr, int ind1, int ind2) {  
  42.         int t = arr[ind1];  
  43.         arr[ind1] = arr[ind2];  
  44.         arr[ind2] = t;  
  45.     }  
  46.   
  47.     public void reverse(int[] arr, int ind1, int ind2) {  
  48.         for (int i = 0; i < (ind2 - ind1) / 2; i++) {  
  49.             swap(arr, ind1 + i, ind2 - 1 - (i));  
  50.         }  
  51.     }  
  52. }  
分享到:
评论

相关推荐

    全排列-非递归算法

    非递归算法的优点在于它可以避免深度过大的调用栈,从而在处理大型数据集时减少内存消耗。这里以1到6的数字为例,我们可以构建一个迭代的解决方案来生成全排列。首先,我们需要一个容器,例如数组或列表,来存储当前...

    N个数全排列的非递归算法

    在提供的文件名称“新建 文本文档.cpp”中,我们可以推测这是一个C++语言的源代码文件,它很可能包含了实现全排列非递归算法的代码。C++是一种强大的面向对象编程语言,非常适合处理这种需要高效计算的问题。 ...

    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): // ...

    java递归实现N个数全排列输出

    在编程领域,全排列是一个经典的算法问题,它涉及到数组或字符串的所有可能的顺序组合。...在学习和实践过程中,你还可以尝试优化算法,例如使用迭代而非递归,或者采用更高效的回溯策略,以提高性能。

    python 数据结构 算法 LeetCode 牛客 面试 编程之美 动态规划 字典树 快速排序 树 字符串 数组 链表 全排列

    * 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 * 二叉查找树-两数之和 * 二叉查找树-中第K小的元素 * 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从有序链表构造平衡的二叉查找...

    全排列算法实现(java\c#\c++,各种主流语言版本)

    对于大型数据集,递归可能会导致栈溢出问题,因此有时会考虑非递归的迭代方法,如回溯搜索或者使用堆栈来存储中间状态,以提高效率。在实际应用中,可以根据具体需求和性能要求选择合适的算法实现。

    python常规方法实现数组的全排列

    在实际应用中,可以考虑使用其他数据结构,如堆栈或队列,或者采用非递归的方法来优化性能。 总的来说,Python中实现数组全排列的方法展示了递归在解决组合问题中的强大能力。通过理解递归的工作原理和全排列的概念...

    C++基础算法荟萃及其实现方法

    包括数组全排列的两种主要方法:逐个追加组合法与递归法;并讲解字符串相关操作以及各种特定整型数组问题,例如求下一个非重复数等,并针对某些特定问题提供了不同场景下的性能优化方式。 适合人群:具有C++基础并对...

    python非递归全排列实现方法

    ### Python非递归全排列实现方法详解 #### 一、引言 在计算机科学与编程领域,全排列问题是一个常见的组合数学问题。全排列是指从给定的n个不同元素中取出m(m≤n)个元素,按照一定的顺序排列起来的方式。递归...

    全排列算法

    5. **优化和变种**:如使用迭代而非递归,或者在特定条件下提前剪枝以减少计算量。 在实际应用中,全排列算法常用于密码学、组合优化、搜索问题等领域。通过这个课程设计,学生不仅能掌握全排列的实现,还能提升...

    matlab经典算法的程序-生成全排列矩阵.zip

    总结来说,MATLAB中的全排列矩阵生成是一个涉及组合优化、递归和非递归算法的问题。通过学习和实践提供的程序,你可以掌握如何在MATLAB环境中高效地生成全排列,这对于提升编程技能和解决相关问题具有重要意义。

    数据结构和算法:字符串

    解决全排列问题可以使用递归算法或非递归算法。递归算法通常基于分治法的思想,通过逐个交换字符来生成新的排列,保证不遗漏任何排列的关键在于递归前保持序列的顺序。而非递归算法则涉及到从字典序最小的排列到字典...

    全排列算法-递归与字典序的实现方法(Java)

    在Java中,我们可以使用递归或者字典序的方法来实现全排列算法。 首先,让我们深入理解递归方法。递归是一种解决问题的方法,它将问题分解成更小的子问题,直到子问题变得足够简单可以直接解决。在全排列问题中,...

    局部搜索解决全排列问题

    局部搜索是一种优化技术,常用于解决复杂问题,如在大量可能解中寻找最优解。在这个实验报告中,局部搜索被应用于...改进方法可能包括非递归算法、动态规划或使用数据结构优化存储和比较过程,以提高效率和避免重复。

Global site tag (gtag.js) - Google Analytics