当前位置:首页 > 资讯 > info5 > 正文

C++输出全排列递归算法详细解释

发表于: 2015-05-06   作者:a358463121   来源:转载   浏览:
摘要: 中心思想:设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}.Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。(1)当n=1时,Perm(R)=(r),其中r是集合R中唯一的元素;(2)当n>1时,Perm(R)可由(r1)+Perm(R1),(r2)+Perm(R2),…,(rn)+Perm(Rn)构成。那么具体程序要怎么实现呢?我们来个实际的

中心思想:
设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}.
Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。
(1)当n=1时,Perm(R)=(r),其中r是集合R中唯一的元素;
(2)当n>1时,Perm(R)可由(r1)+Perm(R1),(r2)+Perm(R2),…,(rn)+Perm(Rn)构成。

那么具体程序要怎么实现呢?我们来个实际的例子,假设有一数列1,2,3,4
那么1,2,3,4的全排列
perm({1,2,3,4})=1perm({2,3,4})+2perm({1,3,4})+3perm({1,2,4})+4perm(1,2,3)
那么我们只要将每个数,与第一个数交换不就可以得到下一个序列了吗?
比如{1,2,3,4}第一个与第二个数交换,那么不就得到2 {1,3,4}了,接下来我们用一个实际的例子说明该程序是怎样运行的

具体算法流程:

数列:{1,2,3} 第一个与第一个交换
可以得到1 {2,3} 将序列{2,3}放进perm函数递归,然后

——递归{2,3}
数列{2,3}第一个与第一个交换
得到2{3} ,输出1,2,3 (此时low=high,因为序列{3}只有一位数,因此输出列表list)
数列{2,3}第一个与第一个交换回来,结果仍然是{2,3}
数列{2,3}第一个与第二个交换
得到3{2},输出1,3,2
{3,2}又第一个与第二个交换回来,变回{2,3}
—–{2,3}递归完毕序列恢复原状{1,2,3}

数列:{1,2,3} 第一个与第二个交换
可以得到2,{1,3}
——递归{1,3}
数列{1,3}第一个与第一个交换
得到1{3} ,输出2,1,3
数列{1,3}第一个与第一个交换回来,结果仍然是{1,3}
数列{1,3}第一个与第二个交换
得到3{1},输出2,3,1
{3,1}又第一个与第二个交换回来,变回{1,3}
—–{1,3}递归完毕
序列{2,1,3}第一个与第二个交换
序列恢复原状{1,2,3}

数列:{1,2,3} 第一个与第三个交换
可以得到3,{1,2}
——递归{1,2}
数列{1,2}第一个与第一个交换
得到1{2} ,输出3,1,2
数列{1,2}第一个与第一个交换回来,结果仍然是{1,2}
数列{1,2}第一个与第二个交换
得到2{1},输出3,2,1
{2,1}又第一个与第二个交换回来,变回{1,2}
—–{1,2}递归完毕
序列{3,1,2}第一个与第二个交换
序列恢复原状{1,2,3}

算法可以简单地写作
perm({1,2,3})=1perm({2,3})+2perm({1,3})+3perm({1,2})
perm({2,3})=2perm({3})+3perm({2})
perm({1,3})=1perm({3})+3perm({1})
perm({1,2})=1perm({2})+2perm({1})

c++代码:

#include <iostream>
using namespace std;
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void perm(int list[],int low,int high){
    if(low==high){   //当low==high时,此时list就是其中一个排列,输出list
        for(int i=0;i<=low;i++)
            cout<<list[i];
        cout<<endl;
    }else{
        for(int i=low;i<=high;i++){//每个元素与第一个元素交换
            swap(list[i],list[low]); 
            perm(list,low+1,high); //交换后,得到子序列,用函数perm得到子序列的全排列
            swap(list[i],list[low]);//最后,将元素交换回来,复原,然后交换另一个元素
        }
    }
}
int main()
{

int list[]={1,2,3};
perm(list,0,2);
return 0;
}

程序结果:

123
132
213
231
321
312

C++输出全排列递归算法详细解释

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一直学习,有时候会感到厌烦,天天呆在自习室,把人都傻了。考研刚刚结束,打算把数据结构再复习复
一个使用递归算法实现全排列 先说一下算法思想: 实现代码如下: #include <iostream> using
排列:从n个元素中任取m个元素,并按照一定的顺序进行排列,称为排列; 全排列:当n==m时,称为全排
排列:从n个元素中任取m个元素,并按照一定的顺序进行排列,称为排列; 全排列:当n==m时,称为全排
全排列在笔试面试中很热门,因为它难度适中,既可以考察递归实现,又能进一步考察非递归的实现,便
不论是哪种全排列生成算法,都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。
#include<iostream> #include<string> using namespace std; void swap(char &a,char &
求全排列问题:如 123 共有 3*2*1 = 6 种组合。 以下程序先是通过递归方式打印出组合。之后再通过非
参考http://www.cnblogs.com/bakari/archive/2012/08/02/2620826.html http://blog.csdn.net/niuox/
原链接:http://blog.csdn.net/MoreWindows 首先来看看题目是如何要求的(百度迅雷校招笔试题) 用C
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号