Full Permutation

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

--百度百科baike.baidu.com/item/%E5%85%A8%E6%8E%92%E5%88%97/4022220

从定义上看，全排列就是将一个集合中的n个元素按不同顺序进行排列，每个元素所处位置有n种可能。例如存在集合s={1,2,3}, 那么其全排列如下：

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

可以看出，一个集合的排列个数为n!。

那么，如果给定一个集合s，我们该如何找到其所有的排列呢？仔细观察上述例子，不难发现，当我们固定元素Si在位置Pj时，则需要找到除Si之外的其它元素的全排列FPi，这样也就得到了Si在位置Pj时的全排列。那么，同样的，我们将所有元素一一至于位置Pj时所得到的全排列组合起来便是集合s的全排列了。即，。所以我们只需要通过递归的方式不断获取元素Si在位置Pj上对应的子集合（除Si外的其它所有元素）的全排列，那么就可以得到集合s的全排列了。如图Figure 1所示，元素Si固定在位置P1。

当然，如果我们允许集合s存在重复的元素，那么集合s的排列个数也必定小于n!。如图Figure 2所示，此时，我们只需要将集合中非重复的元素依次固定在位置P1即可。

附：

full permutation with c++

/*
Author: Future
Date: 2019.08.21
Function: Full Permutation
        input: 3
        output:
              1 2 3
              1 3 2
              2 1 3
              2 3 1
              3 1 2
              3 2 1
*/
#include <iostream>

using namespace std;

bool could_swap(int *arr, int s, int e)
{
    for(int i=s;i<e;i++)
    {
        if(arr[i]==arr[e]) return false;
    }
    return true;
}

void full_permutation(int *arr, unsigned int len, unsigned int start)
{
    if(start == len-1)
    {
        for(unsigned int i=0;i<len;i++)
        {
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
    for(unsigned int i=start;i<len;i++)
    {
        //if arr[i] is equal to any one of the values between start and i(not include i),
        //then there is no need to swap i with start,
        //because the value of arr[i] must have been swapped.
        if(could_swap(arr, start, i))
        {
            swap(arr[start], arr[i]);
            full_permutation(arr, len, start+1);
            //we must restore the state of the array after got the full permutation of sub array
            swap(arr[start], arr[i]);
        }
    }
}

Reference:
[1] https://qwhai.blog.csdn.net/article/details/50986990