Leetcode中级算法-全排列

时间：2022-11-16 10:15:29

全排列算法思想：

1. 全排列的定义和公式：

   从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。由排列的定义，显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数。从n个元素取出n个元素的一个排列，称为一个全排列。

    公式：全排列数f(n) = n! (定义0!=1)

2. 时间复杂度：

   n个数（字符、对象）的全排列一共有n!种，所以全排列算法至少时间O(n!)的。如果要对全排列进行输出，那么输出的时间要O(n∗n!)，因为每一个排列都有n个数据。所以实际上，全排列算法对大型的数据是无法处理的，而一般情况下也不会要求我们去遍历一个大型数据的全排列。

3. 全排列的初始思想

   为了解决一个算法问题，我们选择从基本的想法做起。先回顾一下我们自己是如何写一组数的全排列的：1，3，5，9
首先肯定是 ：

 1 ，[3， 5，9的全排列]
 3 ，[1， 5，9的全排列]
 5 ，[3， 1，9的全排列]
 9 ，[3， 5，1的全排列]

很显然这是一个递归的思路，那么我们根据该想法写出来的初版代码就是：

void permute(vector<int> &nums ,....... ){
    for (int i = 0  ; i != n  ; ++i  )
        {
            swap(nums,0,i); 
            //将第i个数与第一个数交换，从而得到第一个数的所有情况 1，3，5，9
            resove(nums , .....  ); //其后的元素再进行全排列。
        }
    }

给函数加上参数之后就是：

void permute(vector<int> &nums ,int p  , int q ){
    for (int i = 0  ; i != n  ; ++i  )
        {
            swap(nums,0,i); 
            resove(nums , 1, n-1  ); //将后面的1～n-1 个元素再进行全排列。
        }
    }

因为我们不一定就是从第一个元素到最后一个元素进行全排列 ，所以我们必须修改循环条件，使之具有普遍性：

//拿 p～q 之间的元素进行全排列
void permute(vector<int> &nums ,int p  , int q ){
    for (int i = p  ; i !=  q  ; ++i  )
        {
            swap(nums,p,i); 
            resove(nums , p+1, q ); //将后面的 p+1～q 个元素再进行全排列。
        }
    }

OK,下面才是我们的重点内容！！！动脑克啦，

  假如，我们交换到了[3，1，5，9]，接下来需要由5来打头，如果直接将5 和第一个元素交换，那么序列就变成了[5，1，3，9] ,很显然这是极其不正确的。所以我们还需要在由5来打头之前，将[3，1，5，9]进行还原 。 

void permute(vector<int> &nums ,int p  , int q ){
    if(p == q) {
        在这里打印序列即可 ！
    }
    for (int i = p  ; i !=  q  ; ++i  )
        {
            swap(nums,p,i); 
            resove(nums , p+1, q ); 
            swap(nums,p,i);//要还原，确保初始状态一致。 
        }
    }

4.全排列的非去重递归算法

   算法思路：全排列可以看做固定前i位，对第i+1位之后的再进行全排列，比如固定第一位，后面跟着n-1位的全排列。那么解决n-1位元素的全排列就能解决n位元素的全排列了，这样的设计很容易就能用递归实现

题意：

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解决过程中遇到的问题：

c++ STL中怎么定义一个二维向量（vector）

vector<类型> name（size,init_value）;

vector<int> temp（num,0）;//num为向量行数，0为初始化值

vector<vector<int> > test(num,TT);
//前面一个参数表示向量个数，后面参数表示是怎样的一种向量

最后就相当于定义了一个test[num][num]的数组

如何比较快速的求得一个数的阶乘

  1. 定义寄存器变量 
#include<iostream> 
using namespace std;  

int fac(int);  

int main()  
{  
    int n;  

    while(cin>>n)  
    {  
        cout<<n<<"!= "<<fac(n)<<endl;  
    }  

    return 0;  
}  

int fac(int x)  
{  
    register int i,f=1;  //定义寄存器变量 

    for(i=1;i<=x;i++)  
        f*=i;  

    return f;  
}
  1. 利用了数组记录已得到的结果，并在计算下一个结果时利用了已得到的结果。
#include<iostream> 
using namespace std;  

int a[11];  

void init();  

int main()  
{  
    init();  

    int n;  

    while(cin>>n)  
    {  
        cout<<n<<"!= "<<a[n]<<endl;  
    }  

    return 0;  
}  

void init()  
{  
    int i;  

    a[0]=1;  
    for(i=1;i<=10;i++)  
        a[i]=i*a[i-1];  
}
  1. 递归 (略)
  2. 使用静态局部变量
#include<iostream>
using namespace std;

int fac(int);

int main()
{
    int i;

    for(i=1;i<=10;i++)
    {
        cout<<i<<"!= "<<fac(i)<<endl;
    }

    return 0;
}

int fac(int x)
{
    static int f=1;   //静态局部变量

    f*=x;

    return f;
}

ps：推荐第二种！！！！

通过源代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using Iterator = vector<int>::iterator ;
using VV = vector<vector<int> > ;
class Solution {
public:
    void resove(VV  &intVec, vector<int> &nums , 
                Iterator be , Iterator &ed  ) {
        if (be == ed ) {
            intVec.push_back(nums);
        }
        else {
            for (auto it = be ; it != ed ; ++it )
            {
                swap(*it, *be);
                resove(intVec, nums , be + 1 , ed );
                swap(*it, *be);
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        VV  intVec  ; 
        Iterator  be = nums.begin() , ed = nums.end() ;
        resove(intVec, nums , be, ed  ) ;  // 3
        return intVec ;
    }
} ;
标签：

相关文章