给定一组不同的整数，返回所有可能的排列C ++解决方案

Example:
Input: [1,2,3]

Output:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

该问题的解决方案可以通过两种方式解决：

1. 使用递归
2. 使用下一个排列。
3. 使用堆算法 [wiki link]

首先，我们将看一下代码，稍后我将解释所有三种解决方案的工作原理

 #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;
}

输出：

对于所有方法，我们得到相同的输出！

 ( 1 2 3 )
 ( 1 3 2 )
 ( 2 1 3 )
 ( 2 3 1 )
 ( 3 2 1 )
 ( 3 1 2 )

1.使用递归

使用递归很简单。

请考虑以下示例：

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}.

因此，从以上示例中，我们可以看到我们修复了第一个字母，然后反转了其他字母。

我们将使用递归分析如下：

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.使用下一个排列

在解决此问题之前，在这篇文章中， 我已经解释了什么是下一个排列及其工作方式.

使用下一个排列，我们从给定集合的数字中生成下一个更高的数字。

因此，我们的第一步将是按升序对数组进行排序，然后调用库函数，该函数将完成其余的计算。

3.堆’s algorithm

该算法的工作非常简单。

我们遵循以下2个条件来交换元素。

1. 如果数组的大小为偶数，则将第ith个元素与最后一个元素交换。
2. 如果数组的大小为奇数，则将第一个元素与最后一个元素交换。

在第一次迭代中，偶数和奇数之间没有区别。

这是有效的，因为我们不会打扰中间的元素。

在下面评论您的解决方案。

该网站上可用的教程列表：