Given a permutation write c++ program to print permutation just greater than this

belongs to collection: Interview C++ coding problems/challenges | String

mahmoud2506

Save to bookmark

2022-04-29

556

Next Permutation

Given a permutation print permutation just greater than this.

Example:

    Permutation:
    1 3 2 5 4

    Output:
    1 3 4 2 5

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-04-29

need an explanation for this answer? contact us directly to get an explanation for this answer

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

#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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)