Given a collection of distinct integers, return all possible permutations.

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 for this problem can be solved in 2 ways:
1. Using recursion
2. Using next permutation.
3. Using Heap’s algorithm < https://en.wikipedia.org/wiki/Heap%27s_algorithm>

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 =  get_permutation_recursive(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:

Using both 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 he 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 next permutation

Before solving this, in this post, I have explained what is next permutation and how it works.

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

 

Using 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 condition to swap the elements.

1. If the size of the array is even, we swap the ith element with the last element.
2. If the size of the array is odd, then we swap 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.