下一个全排列_下一个排列

川长思鸟来 2023-03-05 09:37 15阅读 0赞

下一个全排列

**Problem statement:**

**问题陈述：**

**Given a permutation print permutation just greater than this.**

**给定一个排列，打印排列就比这个更大。**

**Example:**

**例：**

Permutation:
        1 3 2 5 4
    
        Output:
        1 3 4 2 5

**Solution:**

**解：**

**What is permutation?**

**什么是排列？**

**Permutation** is the process of **arranging** the members of a set into a sequence or order, or, if the set is already ordered, **rearranging** (reordering) its elements. (Ref. [wiki: Permutation][wiki_ Permutation])

**置换**是将集合的成员**排列**为序列或顺序的过程，或者，如果已经对集合进行了排序，则**重新排列** (重新排序)其元素。 (参考[维基：置换][wiki_ Permutation] )

**Example:**

**例：**

Let a set s= {1, 2, 3}
    
        Then it has six permutations which are
        (1, 2, 3)
        (1, 3, 2)
        (2, 1, 3)
        (2, 3, 1)
        (3, 1, 2)
        (3, 2, 1)
        
        This all are ordered 
        
        Thus the next permutation of (1, 3, 2) is (2, 1, 3) and next of (3, 2, 1) is (1, 2, 3). (Yah! It's cyclic)

**Generating Next permutation**

**产生下一个排列**

This problem has a simple but robust algorithm which handles even repeating occurrences. However for this problem we restrict our discussion to single occurrence of numbers in the permutation.

这个问题有一个简单但健壮的算法，可以处理重复的事件。 但是，对于这个问题，我们将讨论限制为排列中数字的单一出现。

**Pre-requisite:**

**先决条件：**

Input permutation of length n

长度为n的输入排列

**Algorithm:**

**算法：**

1.  Find the largest k such that a[k]<a[k+1] , kЄ [0, n-1] //k=-1 initially
    2.  IF
        k is not updated (k is -1 still) that means 
        current is the largest permutation (descending order).
        So the next will be the smallest one (ascending order).
        ELSE
    3.  Find largest l such that a[k]<a[l]
    4.  Swap a[k] and a[l]
    5.  Reverse a[k+1] to a[n-1]

**Example with Explanation:**

**解释示例：**

K initialized to be -1
    
    Example1:
    Permutation:
    1 3 2 5 4
    k=2     //a[k]=2
    l=4     //a[l]>a[k] i.e. 4>2
    After swapping a[k] and a[l]
    Permutation
    1 3 4 5 2
    Reversing a[k+1] to a[n-1]
    1 3 4 2 5 //output 
    
    Example 2:
    Permutation:
    5 4 3 2 1   //largest in the possible permutations
    k=1         //since no such kfound, k is not updated
    Sort the current permutation in ascending order
    Next Permutation
    1 2 3 4 5 //output

**C++ implementation**

**C ++实现**

#include <bits/stdc++.h>
    using namespace std;
    
    //to print a vector
    void print(vector<int> a,int n){
         
    	for(int i=0;i<n;i++)
    		cout<<a[i]<<" ";
    	cout<<endl;
    }
    
    void nextPermutation(vector<int> a,int n){
        
    	int k=-1,l,temp;
    	
    	//finding largest k s.t. a[k]<a[k+1]
    	for(int i=0;i<n-1;i++){
        
    		if(a[i]<a[i+1])
    			k=i;
    	}
    	
    	//if k not updated sort  and print
    	if(k==-1){
        
    		sort(a.begin(),a.end());
    		print(a,n);
    		return;
    	}
    
    	//find the largest l s.t. a[k]<a[l]
    	for(int i=k+1;i<n;i++){
        
    		if(a[i]>a[k])
    		l=i;
    	}
    
    	//swap a[k] and a[l]
    	temp=a[k];
    	a[k]=a[l];
    	a[l]=temp;
    	
    	//print upto a[k]
    	for(int i=0;i<=k;i++)
    		cout<<a[i]<<" ";
    	
    	//reverse printing for a[k+1] to a[n-1] 
    	for(int i=n-1;i>k;i--)
    		cout<<a[i]<<" ";
    	
    	cout<<endl;
    	return;
    }
    
    int main(){
        
    	int n,item;
    
    	cout<<"enter length of permutation\n";
    	scanf("%d",&n);
    	
    	cout<<"enter the permutation leaving spaces betweeen two number\n";
    	vector<int> a;	
    	for(int j=0;j<n;j++){
        
    		scanf("%d",&item);
    		a.push_back(item);
    	}
    	
    	cout<<"Current permutation is:\n";
    	print(a,n);
    	cout<<"next permutation is:\n";
    	nextPermutation(a,n);
    
    	return 0;
    }

**Output**

**输出量**

First run:
    enter length of permutation
    5
    enter the permutation leaving spaces betweeen two number
    1 3 2 5 4 
    Current permutation is:
    1 3 2 5 4
    next permutation is:
    1 3 4 2 5
    
    Second run:
    enter length of permutation
    5
    enter the permutation leaving spaces betweeen two number
    5 4 3 2 1
    Current permutation is:
    5 4 3 2 1
    next permutation is:
    1 2 3 4 5

> 翻译自: [https://www.includehelp.com/icp/next-permutation.aspx][https_www.includehelp.com_icp_next-permutation.aspx]

下一个全排列

[wiki_ Permutation]: https://en.wikipedia.org/wiki/Permutation
[https_www.includehelp.com_icp_next-permutation.aspx]: https://www.includehelp.com/icp/next-permutation.aspx