给定含有N个互不相同元素的序列,输出这N个元素的所有排列(全排列)。

以字符串"abc"为例,全排列包括"abc”,“acb”,“bac”,“bca”,“cab”,“cba"这6个结果。
从排列组合来计算6=3!=3*2*1,也就是我们依次选择3个元素:

  • 第一个元素有3种选择(a,b,c),假设选择c
  • 第二个元素只有2种选择(a,b),假设选择b
  • 第三个元素只有1种选择(a)

递归

首先我们采用递归(+回溯)的方式实现。
假设我们已经完成N-1个元素的全排列,那么怎么完成N个元素的全排列?

由上面的简介可知,N个元素的全排列结果数目等于N! = N*(N-1)!。
也就是说遍历任选N个元素中的一个+剩下N-1个元素全排列。

版本一

代码实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void permuteV1(char arr[], int size, int selIdx)
{
    if (selIdx >= size)
    {
        for (int idx=0; idx<size; idx++)
        {
            cout<<arr[idx];
        }
        cout<<endl;

        return;
    }

    for (int idx=selIdx; idx<size; idx++)
    {
        // selIdx之前为已选择元素,之后(包括selIdx)为待选择元素
        // 从待选择元素从选一个交换到selIdx,产生新的全排列
        swap(arr[selIdx], arr[idx]);
        permuteV1(arr, size, selIdx+1);

        // 上面选择了idx元素,接下来选择下一个待选择元素(idx+1),首先需要撤销选择idx元素
        swap(arr[selIdx], arr[idx]);
    }
}

对于"abc",上述代码输出结果为"abc","acb","bac","bca","cba","cab"。
细心的朋友可能会发现先输出"cba",然后再输出"cab"。
是的,上述代码输出次序并不是按照 字典序

版本二

在序列本身有序(升序)的前提下,把上面的swap改成如下操作即可实现字典序输出:

  • 把[selIdx, idx)区间的元素整体后移一位
  • 再把idx元素放到selIdx位置

代码实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void selElem(char arr[], int selIdx, int idx)
{
    int offset = idx-selIdx;
    char backup = arr[idx];

    memmove(arr+selIdx+1, arr+selIdx, offset);
    arr[selIdx] = backup;
}

void unselElem(char arr[], int selIdx, int idx)
{
    int offset = idx-selIdx;
    char backup = arr[selIdx];

    memmove(arr+selIdx, arr+selIdx+1, offset);
    arr[idx] = backup;
}

void permuteV2(char arr[], int size, int selIdx)
{
    if (selIdx >= size)
    {
        for (int idx=0; idx<size; idx++)
        {
            cout<<arr[idx];
        }
        cout<<endl;

        return;
    }

    for (int idx=selIdx; idx<size; idx++)
    {
        // selIdx之前为已选择元素,之后(包括selIdx)为待选择元素
        // 从待选择元素从选一个移到selIdx,产生新的排列
        selElem(arr, selIdx, idx);
        permuteV2(arr, size, selIdx+1);

        // 上面选择了idx元素,接下来选择下一个待选择元素(idx+1),首先需要撤销选择idx元素
        unselElem(arr, selIdx, idx);
    }
}

当然从效率上来说,相比swap交换,上述代码效率有所降低。

非递归

要以非递归方式实现全排列,首先要解决的是根据当前排列得到下一个排列。
另外需要注意的是全排列中所有排列也是有顺序的,比较自然的想法就是某种意义上的"升序”。
以"abc"序列来说,“bac"应该在"bca"之前,因为这两个排列都以b开头,由后面的a和c决定顺序。

字典序

上述顺序其实就是 字典序,简单来说就是以字母顺序依次比较序列中元素,直到决出顺序。

那么如何得到字典序的下一个排列?算法如下:

  • 从排列末尾寻找相邻升序子序列seq[i]<seq[i+1],如果不存在说明是最后的排列
  • 从排列末尾寻找seq[i]<seq[j] (由上述步骤可知j一定存在)
  • 交换seq[i]与seq[j]
  • 反转seq[i+1]之后的元素

其实i+1元素前面是升序,后面是降序。
降序说明子序列已经遍历完,i元素需要更新更大的值,所以从右边选取。
更新完i元素之后反转是因为要开始新的一轮子序列全排列(降序反转后为升序)。

代码实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int hasNextPermutation(char arr[], int size)
{
    int i = size-2;
    int j = 0;

    // find seq[i]<seq[i+1]
    while (0<=i)
    {
        if (arr[i] < arr[i+1])
        {
            break;
        }

        i--;
    }

    // not found
    if (0>i)
    {
        return 0;
    }

    // find seq[j]>seq[i]
    j=size-1;
    while (arr[i] >= arr[j])
    {
        j--;
    }

    swap(arr[i], arr[j]);
    reverse(arr+i+1, arr+size);

    return 1;
}

void permuteIter(char arr[], int size)
{
    do
    {
        for (int idx=0; idx<size; idx++)
        {
            cout<<arr[idx];
        }
        cout<<endl;
    } while (hasNextPermutation(arr, size));
}

STL之next_permutation

实际上STL已经提供了这样的算法,通过next_permutation可以获取下一个排列。
示例代码如下:

1
2
3
4
5
6
7
void permuteStl(string& str)
{
    do
    {
        cout<<str<<endl;
    } while(next_permutation(str.begin(), str.end()));
}

变种

上述讨论的序列中元素是互不相同的,其中一种变种就是允许重复元素。
由于非递归采用的是字典序保持"升序”,所以不存在问题。
而递归方法会重复打印,需要调整为在待选择元素中选择下一个与当前选择不同的元素。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void permuteV2dup(char arr[], int size, int selIdx)
{
    if (selIdx >= size)
    {
        for (int idx=0; idx<size; idx++)
        {
            cout<<arr[idx];
        }
        cout<<" ";

        return;
    }

    for (int idx=selIdx; idx<size; idx++)
    {
        // selIdx之前为已选择元素,之后(包括selIdx)为待选择元素
        // 从待选择元素从选一个移到selIdx,产生新的排列
        selElem(arr, selIdx, idx);
        permuteV2dup(arr, size, selIdx+1);

        // 上面选择了idx元素,接下来选择下一个待选择元素(idx+1),首先需要撤销选择idx元素
        unselElem(arr, selIdx, idx);

        // 选择下一个与当前选择不同的元素
        while (idx+1<size && arr[idx]==arr[idx+1])
        {
            idx++;
        }
    }
}