`

全排列算法非递归实现和递归实现 (C++)

阅读更多

 

(一)非递归全排列算法

基本思想是:
    1.找到所有排列中最小的一个排列P.
    2.找到刚刚好比P大比其它都小的排列Q,
    3.循环执行第二步,直到找到一个最大的排列,算法结束.
下面用数学的方法描述:
给定已知序列 P =  A1A2A3An ( Ai!=Aj , (1<=i<=n  , 1<=j<=n, i != j  ) )
找到P的一个最小排列Pmin = P1P2P3Pn  有  Pi > P(i-1) (1 < i <= n)
从Pmin开始,总是目前得到的最大的排列为输入,得到下一个排列.
方法为:
1.从低位到高位(从后向前),找出“不符合趋势”的数字。即找到一个Pi,使Pi < P(i+1)。
  若找不到这样的pi,说明我们已经找到最后一个全排列,可以返回了。
2.在 P(i+1)P(i+2)Pn 中,找到一个Pj,便得 Pj"刚刚好大于"Pi. 
  ("刚刚好大于"的意思是:在 P(i+1)P(i+2)Pn 中所有大于Pi的元素构成的集合中最小的元素.)
3.交换 Pi , Pj 的位置.注意:此处不改变i和j的值,改变的是Pi和Pj.
4.交换后, P1P2P3Pn  并不是准确的后一个排列。因为根据第1步的查找,我们有P(i+1) > P(i+2) > . > Pn
  即使进行了Pi和Pj的交换,这仍然是这一部分最大的一个排列。将此排列逆序倒置(变成最小的排列)即为所求的下一个排列.
5.重复步骤1-4,直到步骤1中找不到“不符合趋势”的数字.

 

//交换数组a中下标为i和j的两个元素的值

void swap(int* a,int i,int j)

{

    a[i]^=a[j];

    a[j]^=a[i];

    a[i]^=a[j];

}

 

//将数组a中的下标i到下标j之间的所有元素逆序倒置

void reverse(int a[],int i,int j)

{

    for(;i<j;++i,--j)

    {

         swap(a,i,j);

    }

}

 

void print(int a[],int length)

{

    for(int i=0;i<length;++i)

         cout<<a[i]<<" ";

    cout<<endl;

}

 

//求取全排列,打印结果

void combination(int a[],int length)

{

    if(length<2) return;

 

    bool end=false;

    while(true)

    {

         print(a,length);

        

         int i,j;

         //找到不符合趋势的元素的下标i

         for(i=length-2;i>=0;--i)

         {

             if(a[i]<a[i+1]) break;

             else if(i==0) return;

         }

 

         for(j=length-1;j>i;--j)

         {

             if(a[j]>a[i]) break;

         }

        

         swap(a,i,j);

         reverse(a,i+1,length-1);

    }

}

 

(二)递归算法

E= {e1 , ..., en }表示个元素的集合,我们的目标是生成该集合的所有排列方式。令Ei E中移去元素以后所获得的集合,perm (X表示集合中元素的排列方式,ei . p e r m(X)表示在perm (X中的每个排列方式的前面均加上ei 以后所得到的排列方式。例如,如果E= {a, b, c},那么E1= {b, c}perm (E1 ) = ( b cc b)e1 .perm (E1) = (a b ca c b)。对于递归的基本部分,采用= 1。当只有一个元素时,只可能产生一种排列方式,所以perm (E) = ( e),其中中的唯一元素。当> 1时,perm (E) = e1 .perm (E1 ) +e2 .p e r m(E2 ) +e3.perm (E3) +  +en .perm (En )。这种递归定义形式是采用perm (X来定义perm (E), 其中每个包含n- 1个元素。至此,一个完整的递归定义所需要的基本部分和递归部分都已完成。

n= 3并且E=abc)时,按照前面的递归定义可得perm (E) =a.perm ( {bc} ) +b.perm ( {a,c} ) +c.perm ( {ab} )。同样,按照递归定义有perm ( {bc} ) =b.perm ( {c} ) +c.perm ( {b}), 所以a.perm ( {bc} ) = ab.perm ( {c} ) + ac.perm ( {b}) = a b . c ac.b = (a b ca c b)。同理可得b.perm ( {ac}) = ba.perm ( {c}) + bc.perm ( {a}) = b a . c b c . a = (b a cb c a)c.perm ( {ab}) =ca.perm ( {b}) + cb.perm ( {a}) = c a . b c b . a = (c a bc b a)。所以perm (E) = (a b ca c bb a cb c a,c a bc b a)。注意a.perm ( {bc} )实际上包含两个排列方式:abc a c b是它们的前缀,perm ( {bc} )是它们的后缀。同样地,ac.perm ( {b}) 表示前缀为a c、后缀为perm ( {b}) 的排列方式。程序1 - 1 0把上述perm (E的递归定义转变成一个C++ 函数,这段代码输出所有前缀为l i s t [ 0k-1], 后缀为l i s t [ km] 的排列方式。调用Perm(list, 0, n-1) 将得到list[0: n-1] 的所有n! 个排列方式,在该调用中,k=0, m= n - 1,因此排列方式的前缀为空,后缀为list[0: n-1] 产生的所有排列方式。当k =m 时,仅有一个后缀l i s t [ m ],因此list[0: m] 即是所要产生的输出。当k<m时,先用list[k] l i s t [ km] 中的每个元素进行交换,然后产生list[k+1: m] 的所有排列方式,并用它作为list[0: k] 的后缀。S w a p是一个inline 函数,它被用来交换两个变量的值

 

template <class T>

inline void Swap(T& a, T& b)

{

    // 交换ab

    T temp = a; a = b; b = temp;

}

 

template<class T>

void Perm(T list[], int k, int m)

{

    //生成list [km ]的所有排列方式

    int i;

    if (k == m)

    {

         //输出一个排列方式

         for (i = 0; i <= m; i++)

             cout << list [i];

         cout << endl;

    }

    else // list[km ]有多个排列方式

    {

         // 递归地产生这些排列方式

         for (i=k; i <= m; i++)

         {

             Swap (list[k], list[i]);

             Perm (list, k+1, m);

             Swap (list [k], list [i]);

         }

    }

}

分享到:
评论

相关推荐

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

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

    全排列算法的非递归实现与递归实现的方法(C++)

    在C++中,我们可以使用非递归和递归两种方法实现全排列算法。 ### 非递归全排列算法 非递归实现的核心思想是通过不断调整已排序的序列,找到下一个更大的排列。算法主要分为以下几步: 1. 找到当前排列中的最小...

    c++实现全排列

    C++实现全排列算法详解 C++实现全排列是算法中的一种常见问题,解决该问题可以使用递归和非递归两种方法。递归方法可以通过不断地选择每个元素来生成全排列,但是这种方法在元素个数很多时很容易造成堆栈溢出,因此...

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

    这些实现遵循了基本的全排列算法思路,即通过递归和回溯来生成所有可能的排列。对于大型数据集,递归可能会导致栈溢出问题,因此有时会考虑非递归的迭代方法,如回溯搜索或者使用堆栈来存储中间状态,以提高效率。在...

    全排序算法c++递归实现

    1. **迭代替代递归**:通过迭代而非递归的方法来生成全排列可以显著减少函数调用的开销。 2. **避免重复计算**:在递归过程中记录已生成的排列,以避免重复计算。 3. **并行处理**:利用多线程或多进程技术来并行...

    全排列生成算法字典序vc++源码

    在实际应用中,全排列生成算法可能需要优化以处理大规模数据,比如使用非递归方法,或者通过并行化来提高效率。此外,如果需要按字典序快速查找或插入特定排列,可以考虑使用二叉堆或平衡搜索树等数据结构。 总结来...

    非递归的输出1-N的全排列实例(推荐)

    网易游戏笔试题算法题之一,可以用C++,Java,Python,由于Python代码量较小,于是我选择Python语言。 算法总体思路是从1,2,3……N这个排列开始,一直计算下一个排列,直到输出N,N-1,……1为止 那么如何计算给定排列...

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

    内容概要:本系列专栏汇总了 C++ 笔试题目和一系列基础算法及其可运行的实例代码。包括数组全排列的两种主要方法:逐个追加组合法与递归法;并讲解字符串相关操作以及各种特定整型数组问题,例如求下一个非重复数等...

    QuanPaiLie.rar_K._perm(list_x_M)_全排列

    在实际应用中,`www.pudn.com.txt`可能是相关代码或文档的说明,而`QuanPaiLie`可能是实现全排列算法的源代码文件,可能包含了类、函数和其他必要的数据结构。 理解全排列递归算法的关键在于掌握递归的基本思想和...

    8594有重复元素的排列问题

    题目 "8594有重复元素的排列问题" 是一道编程题,主要涉及计算机科学...对于更大的数据规模,可以考虑使用更高效的算法,如基于堆或哈希表的非递归解决方案。在实际编程竞赛或工程应用中,优化算法的性能是非常重要的。

    ACM编程题模板和各种经典算法数据结构实现代码

    ### ACM编程题模板和各种经典算法数据结构实现代码解析 #### 概述 这份文档源自吉林大学ACM/ICPC团队,旨在为学习ACM竞赛的学生提供一系列算法和数据结构的实现代码。文档包含了多种算法及其应用实例,覆盖了图论...

    精心整理的C++授课课件

    8. **CPP_15_全排列.ppt** - 讨论全排列问题,介绍算法实现,比如回溯法,以及如何使用C++编程来解决这类问题。 9. **CPP_16_位运算.ppt** - 介绍位运算符(如与、或、异或、左移、右移等)及其在二进制操作中的...

    C++编程24点

    5. **递归与回溯**:24点的算法通常采用深度优先搜索(DFS)配合递归实现。遍历所有可能的运算组合,当找到可行解时返回,若无解则回溯。 6. **组合与排列**:计算24点涉及到四个数的不同组合和顺序,这需要理解...

    Untitled1.zip_数据结构_C/C++_

    数据结构是计算机科学中的核心概念,它涉及到如何高效地存储和组织数据,以便于...理解并掌握如何在C/C++中实现全排列算法,不仅能提升编程技巧,还能加深对数据结构和算法的理解,对于软件开发和系统设计都大有裨益。

    《算法设计》课程解题报告.docx

    非递归算法实现 #### 尾递归优化 为了提高算法效率,可以对递归算法进行非递归化处理。具体而言,通过循环的方式逐步更新排列arr'和累积字典序值,从而避免重复调用递归函数。 ```cpp int dictRank(int* arr, int...

    C++培训板书原版(jwk推荐)

    - **全排列算法**:通过多层循环实现对特定集合的所有可能排列,如使用三个嵌套循环分别将变量A、B、C从1到n循环,并确保它们互不相同。 - **复杂的for循环结构**:展示了一种非标准的for循环结构,该结构包含了初始...

    南邮ACM算法与数据结构设计第5讲PPT教案学习.pptx

    **枚举全排列的实现**通常采用递归方法。在C程序中,首先读入数组,然后使用`qsort`进行排序。`cmp`函数用于定义比较规则,以确保排列的顺序。`print_permutation`函数是递归的核心,它尝试在当前位置填充所有可能的...

    ACM/ICPC常用算法的代码库(吉林大学版,强烈推荐)

    它包含了多种算法及其实现方式,适用于ACM/ICPC参赛者的学习和参考。这份代码库不仅涵盖了图论、网络流、数据结构等核心领域,还涉及了数论、字符串匹配等其他重要方面。 #### 图论 ##### Graph图论 - **DAG的深度...

Global site tag (gtag.js) - Google Analytics