C++ Program to Next_permutation for All Arrangements with Explanation

Next_permutation for All Arrangements

Hard C++ STL 35 views

Explanation Complexity

Problem Statement

Generate next lexicographic permutation.
Real Life: Finding all possible arrangements.

Input Format

An integer n (size of array)
Then n integers (current permutation).

Output Format

Next lexicographic permutation of the array.
If no next permutation exists, print the smallest permutation.

Example

Input

3
1 2 3

Output

1 3 2

Constraints

• n ≥ 1

• Elements are integers

• Array represents a valid permutation

Concept Explanation

A lexicographic permutation means dictionary order.
The “next” permutation is the next greater arrangement using the same elements.
This is useful when generating all possible arrangements one by one.

Step-by-Step Explanation

1.Start from the right end of the array.

2.Find the first index i such that arr[i] < arr[i+1].

• If no such index exists, the array is the last permutation.

3.Again from the right, find index j such that arr[j] > arr[i].

4.Swap arr[i] and arr[j].

5.Reverse the elements from index i+1 to the end of the array.

6.The resulting array is the next lexicographic permutation.

Concept Explanation

Step-by-Step Explanation

Input / Output Format

Input Format

An integer n (size of array)
Then n integers (current permutation).

Output Format

Next lexicographic permutation of the array.
If no next permutation exists, print the smallest permutation.

Constraints

• n ≥ 1

• Elements are integers

• Array represents a valid permutation

Examples

Input:

3 1 2 3

Output:

1 3 2

Example Solution (Public)

C++

void stl_q15_next_permutation() {
    vector<int> numbers = {1, 2, 3};
    
    cout << "All permutations:" << endl;
    do {
        for(int num : numbers) {
            cout << num << " ";
        }
        cout << endl;
    } while(next_permutation(numbers.begin(), numbers.end()));
}


int main() {
    cout << "=== C++ PRACTICE QUESTIONS ===" << endl;
    cout << "All topics covered with detailed explanations!" << endl;
    
    return 0;
}

Official Solution Code

void stl_q15_next_permutation() {
    vector<int> numbers = {1, 2, 3};
    
    cout << "All permutations:" << endl;
    do {
        for(int num : numbers) {
            cout << num << " ";
        }
        cout << endl;
    } while(next_permutation(numbers.begin(), numbers.end()));
}


int main() {
    cout << "=== C++ PRACTICE QUESTIONS ===" << endl;
    cout << "All topics covered with detailed explanations!" << endl;
    
    return 0;
}

Please login to submit solutions.