全排列

以你之姓@ 2022-07-17 15:25 256阅读 0赞

# 全排列 #

给出一个字符串或整数数组，对这个字符串或整数数组进行全排列  
例如：\{1， 2， 3\} 数组，对这个整数数组进行全排列。

# 递归实现 #

## 实现 ##

/* 
     * 递归输出序列的全排列 
     */  
    void FullArray(char* array, size_t array_size, unsigned int index)  
    {  
        if(index >= array_size)  
        {  
            for(unsigned int i = 0; i < array_size; ++i)  
            {  
                cout << array[i] << ' ';  
            }  
    
            cout << '\n';  
    
            return;  
        }  
    
        for(unsigned int i = index; i < array_size; ++i)  
        {  
            swap(array[i], array[index]);  
    
            FullArray(array, array_size, index + 1);  
    
            swap(array[i], array[index]);  
        }  
    }

// Test
    int main()
    {
        int array[] = { 1, 2, 3};
        fullArray(array, sizeof(array)/sizeof(array[0]), 0);
    }

// 打印结果
    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 2 1
    3 1 2

## 蕴含的思想 ##

### 分治法思想 ###

1.  问题的规模缩小到一定的程度就可以容易地解决。
2.  问题可以分解为若干个规模较小的相同问题，即该问题有**最优子结构** \[2\]性质。
3.  利用该问题分解出的子问题的解可以合并为该问题的解。
4.  该问题所分解出的各个子问题是相互独立的，即自问之间不包含公共子问题。

分治法的三个步骤：

1.  分解（Divide）：将原问题分解为若干子问题，这些子问题都是原问题规模较小的实例。
2.  解决（Conquer）：递归地求解各子问题。如果子问题规模足够小，则直接求解。
3.  合并（Combine）：将所有子问题的解合并为原问题的解。

## 分治在全排列中的应用 ##

### 问题： ###

array = \{1, 2, 3, … n \}的全排列，心算手写非常简单，但是编写程序却无从下手。

### 分析过程： ###

1.  如对array = \{1, 2, 3, … , n\} 数组进行全排列，可以先确定数组索引为 0 位置上的数字，然后再确定其他索引位置上的数字。
2.  划分成了两个子问题：
    
    1.  确定`array数组索引0` 位置上数字全排列问题
    2.  确定`array数组索引1~索引n-1`位置上数字的全排列子问题
    3.  很明显，这里划分成了两个与原问题相同的子问题
    4.  注意的是，划分子问题有很强的依赖性，即必须先解决`array数组索引0` 位置上数字全排列问题，然后才能解决`array数组索引1~索引n-1`位置上数字的全排列子问题
3.  确定`array数组索引0`位置上的数字是一个规模较小的子问题
    
        // 解决数组索引0位置上的数字
        // 注：原array索引为0位置上的数字当然可以为全排列的首数字
        for (int i = 0; i < array_size; i++) {
            swap(array[i], array[0]); 
        } 
        // 同理确定`索引index`位置上的数字，但注意，i之前位置上的数字必须已经确定
        for (int i = index; i < array_size; i++) {
            swap(array[i], array[index]);
        }
4.  确定`array数组索引1~索引n-1`位置上数字全排列，同理可继续按照上面的方式划分子问题：即`array数组索引1`位置上数字的全排列问题和`array数组索引２~索引n-1`位置上数字的全排列问题。
5.  每次确定`array数组索引index`（index：0~n-1）位置上的数字之后，`array数组index+1~n-1`位置上的数字也确定之后，必须恢复原数组的模样，之后给`array数组索引index`位置上确定新的数字时，确保原数字数组没有被打乱（因为直接使用了swap方式修改了index位置的值）。

for (int i = index; i < array_size; i++) {
        swap(array[i],array[index]);
        fullArray(array, array_size, index+1);
        swap(array[i], array[index]);
    }

--------------------

注：2016.11.1补充

# 有重复字符的全排列 #

## 去重复字符的递归算法 ##

例如：1223的全排列  
1 - 223  
2 - 123  
3 - 221

带重复字符的全排列就是每个字符分别与它后面`非重复出现的字符`交换。即：第 i 个字符（前）与第 j 个字符（后）交换时，要求\[i, j)中没有与第 j 个字符相等的数。

bool isDuplicate(int* a, int lo, int hi) {
        while (lo < hi) {
            if (a[lo] == a[hi])
                return true;
            lo++;
        }
        return false;
    }
    
    void Permutation(int* a, int size, int index)
    {
        if (index == size) {
            for (int i = 0; i < size; i++) 
                cout << a[i] << endl;
            return;
        }
    
        for (int i = index; i < size; i++) {
            if (isDuplicate(a, index, i))
                continue;
            swap(a[i], a[index]);
            Permutation(a, size, index+1);
            swap(a[i], a[index]);
        }
    }

## 重复数字的全排列递归算法时间复杂度 ##

记`Permutation函数`的时间复杂度函数为f(n),n为问题规模  
则 f(n) = nf(n-1) + n^2

# 非递归实现 #

# 参考资料 #

\[1\] [Divide and Conquer - 分治法][Divide and Conquer -]  
\[2\] [什么是动态规划？动态规划的意义是什么？][Link 1]  
\[3\] [时间复杂度][Link 2]

[Divide and Conquer -]: http://algorithm.yuanbin.me/zh-hans/basics_algorithm/divide_and_conquer.html
[Link 1]: https://www.zhihu.com/question/23995189
[Link 2]: http://blog.csdn.net/booirror/article/details/7707551/