算法设计与分析——递归与分治策略——全排列

秒速五厘米 2022-10-22 14:55 151阅读 0赞

**算法设计与分析——递归与分治策略——全排列**

全排列问题的解决是通过分治与递归思想来解决的  
首先判断是否递归到了最后一位，如果递归到了最后一位，则输出他当前的全排列序列。  
如果没有到达最后一位，则循环的交换该第K个元素与其后面的所有元素，每次交换后立即进入递归程序，进入下一层的递归。  
代码1：

#include<iostream>
    using namespace std;
    template <class Type>
    void perm(Type *list,int k,int m)
    {
        
    	if(k == m)//此时递归到了最后一层 
    	{
        
    		for(int i=0;i<=m;i++)
    		{
        
    			cout<<list[i]<<" ";
    		} 
    		cout<<endl;
    	}
    	else
    	{
        
    		for(int i=k;i<=m;i++)//将传来的参数区间的，进行该位置的所有全排列 
    		{
        
    			swap(list[k],list[i]);//交换位置 
    			perm(list,k+1,m);//递归嵌套到下一层去，即少一位后的全排列 
    			swap(list[k],list[i]);//回溯的思想，返回到原来没有排列的样子 
    		}
    	}
    }
    int main()
    {
        
    	int n;
    	cout<<"输入需要进行全排列的数据长度："<<endl;
    	cin>>n;
    
    	int list[n];
    	cout<<"输入需要进行全排列的数据:"<<endl;
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>list[i];
    	 } 
    	 cout<<"输出全排列的结果："<<endl; 
    	 perm(list,0,n-1);
    	 return 0;
    	
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

#include<bits/stdc++.h>
    using namespace std;
    int number=0;
    void arrange(vector<int> &nums,int left,int right)
    {
        
        if(left==right)
        {
        
            for(auto a:nums)
            {
        
                cout << a << " ";
            }
            cout << endl;
            number++; 
        }
        else
        {
        
            for (int i = left; i <= right; i++)
            {
        
                swap(nums[left], nums[i]);
                arrange(nums, left + 1, right);
                swap(nums[left], nums[i]);
            }
        }
    }
    
    int main()
    {
        
        vector<int> nums = {
        1,2,3};
        int count = nums.size()-1;
        arrange(nums, 0,count);
        cout<<"全排列一共有"<<number<<"个排列"<<endl; 
        system("pause");
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221022/79464c7af66f4f2fa5a38c6c88032204.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221022/d4a3e17f1d104bb398cebaefce6189a0.png