Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
The solution to this problem can be solved in 2 ways:
- Using recursion
- Using the next permutation.
- Using Heap’s algorithm [wiki link]
First, we shall look at the code, later I shall explain about the working of all three the solutions
#include<iostream> #include <vector> using namespace std; void permutation_recursive(vector<int> &input_set, int begin, vector<vector<int> > &final_result_set) { //base condition for recursive function if (begin >= input_set.size()) { // add the number pair to the final result set. final_result_set.push_back(input_set); return; } // i will be the index of each fixed digit for (int i = begin; i < input_set.size(); i++) { swap(input_set[begin], input_set[i]); permutation_recursive(input_set, begin + 1, final_result_set); // reset the swapped numbers swap(input_set[begin], input_set[i]); } } vector<vector<int> > get_permutation_recursive(vector<int> &input_set) { vector<vector<int> > final_result_set; permutation_recursive(input_set, 0, final_result_set); return final_result_set; } vector<vector<int> > using_next_permutation(vector<int>& input_set) { vector<vector<int> > final_result_set; sort(input_set.begin(),input_set.end()); do { final_result_set.push_back(input_set); } while (next_permutation(input_set.begin(), input_set.end())); return final_result_set; } vector<vector<int> > get_permutation_heaps_algorithm_recursive(vector<int>& input_set, int size, vector<vector<int> >& final_result_set) { if(size == 1) { final_result_set.push_back(input_set); return final_result_set; } for(int i=0; i<size; i++) { cout<<endl; get_permutation_heaps_algorithm_recursive(input_set, size-1, final_result_set); if(size%2==1) swap(input_set[0],input_set[size-1]); else swap(input_set[i],input_set[size-1]); } return final_result_set; } vector<vector<int> > get_permutation_heaps_algorithm(vector<int>& input_set) { vector<vector<int> > final_result_set; int n = input_set.size(); final_result_set = get_permutation_heaps_algorithm_recursive(input_set, n, final_result_set); return final_result_set; } int main() { vector<int> input_set; input_set.push_back(1); input_set.push_back(2); input_set.push_back(3); //vector<vector<int> > final_set = get_permutation_recursive(input_set); //vector<vector<int> > final_set = using_next_permutation(input_set); vector<vector<int> > final_set = get_permutation_heaps_algorithm(input_set); // print the output for (int i = 0; i < final_set.size(); i++) { if (final_set[i].size() > 0) { cout << " ( "; for (int j = 0; j < final_set[i].size(); j++) cout << final_set[i][j] << " "; cout << ")"; } cout<<endl; } return 0; }
Output:
For all the methods, we get the same output !!
( 1 2 3 ) ( 1 3 2 ) ( 2 1 3 ) ( 2 3 1 ) ( 3 2 1 ) ( 3 1 2 )
1. Using recursion
Using recursion is simple.
Consider the examples below:
1 -> 1 1, 2 -> {1, 2}, {2, 1} 1, 2, 3 -> {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}.
So from the above examples, we can see that we fix the first letter, then reverse the other letters.
We shall analyze the same using recursion as below:
begin = 0 nums = {1, 2} result = NULL nums.size = 2 pass 1: for(i =0; i < 2; i++) swap(a[0], a[0]) permutation_recursive({1, 2}, 1, null) //resursively call the same function begin = 1 nums = {1, 2} result = NULL nums.size = 2 swap(a[1], a[1]) permutation_recursive({1, 2}, 1, null) //resursively call the same function begin = 2 nums = {1, 2} result = NULL nums.size = 2 if (begin >= nums.size) true, push {1, 2} to result set. Return both the recursive function
pass 2: begin = 0 nums = {1, 2} result = {1, 2} nums.size = 2 for(i =1; i < 2; i++) swap(a[1], a[0]) permutation_recursive({2, 1}, 1, null) //resursively call the same function begin = 1 nums = {2, 1} result = NULL nums.size = 2 swap(a[1], a[1]) permutation_recursive({2, 1}, 2, null) //resursively call the same function begin = 2 nums = {2, 1} result = {1, 2} nums.size = 2 if (begin >= nums.size) true, push {2, 1} to result set. Return both the recursive function Final result set will be ({1,2}, {2, 1})
2. Using the next permutation
Before solving this, in this post, I have explained what is the next permutation and how it works.
Using the next permutation, we generate the next higher number, from the digits of the given set.
Hence our first step will be sorting the array in ascending order, then call the library function, that will do the rest of the calculation.
3. Heap’s algorithm
The working of this algorithm is very simple.
We follow below 2 conditions to swap the elements.
- If the size of the array is even, we swap the ith element with the last element.
- If the size of the array is odd, then we swap the first element with the last element.
In the first iteration, there is no difference between even and odd.
This is efficient because we don’t disturb the middle elements.
Comment below with your solutions.
No Responses