全排列

﹏ヽ暗。殇╰゛Y 2022-06-17 06:19 248阅读 0赞

方法一:采用递归的方式例子1、将数组int arr\[4\]=\{1,2,3,4\}进行全排列

static int n = 0;
    void Perm(int *arr, int k, int m)
    {
    	if (k ==m)
    	{
    		for (int i = 0; i <m; i++)
    		{
    			cout << arr[i];
    		}
    		cout << endl;
    		++n;
    	}
    	else
    	{
    		for (int j = k; j < m; j++)
    		{
    			swap(arr[k], arr[j]);
    			Perm(arr, k + 1, m);
    			swap(arr[k], arr[j]);
    		}
    	}
    }

递归的思想：设置k从0开始，然后再令j=k，只要k<m那么就一直进行递归，直到递归到k=m的时候进行打印数组。这种递归是在循环里进行递归。1\{2，3，4\}第一次swap(arr\[0\],arr\[0\])那么此时就是保持数组中1不变，然后进入循环递归将其他的进行排列组合再打印出来。2\{1，3，4\}第一次swap(arr\[0\],arr\[1\])，那么此时保持数组中的2不变，然后进入循环递归将其他的进行排列组合再打印出来。3\{2，1，4\}第一次swap(arr\[0\],arr\[1\])，那么此时保持数组中的3不变，然后进入循环递归将其他的进行排列组合再打印出来。4\{2，3，1\}第一次swap(arr\[0\],arr\[1\])，那么此时保持数组中的4不变，然后进入循环递归将其他的进行排列组合再打印出来

.第二种方式：使用STL中的库函数bool next\_permutation (BidirectionalIterator first,BidirectionalIterator last );

void permutation(int *arr,int len)
    {
    	do
    	{
    		for (int i = 0; i < len; i++)
    		{
    			cout << arr[i];
    		}
    		cout << endl;
    	} while (next_permutation(arr, arr + len));
    }

这种方式的前提是本身是一个升序的有序序列  解法很简单，就是将数组排序（升序），然后从尾到头找到第一个可以交换的位置  1234排序  先从尾部3开始从比较比3大的数字进行交换  1243  此时再将之前的4 3颠倒连接在12后面变成1234  然后继续找2 3 4 中比2小的数字进行交换得到1 3 2 4  再将2 4比较之后交换得到1 3 4 2  再将3 2 4中较小的颠倒链接在1之后即为1 4 2 3  再将1 4 2 3中的2 3交换的到1 4 3 2

![Center][]

[Center]: /images/20220617/6f5ac7618e174872bbd10b0078c9b75b.png