算法的乐趣之分治法

分治法（Divide and Conquer）

分治法的设计思想是将无法着手解决的大问题分解成一系列规模较小的相同问题，然后逐个解决小问题，即所谓分而治之。

在很多情况下，分治法都会使用递归的方式对问题逐级分解，但是在每个子问题的层面上，分治法基本上可以归纳为三个步骤。

• 分解：将问题分解为若干个规模较小，相互独立且与原问题形式相同的子问题，确保各个子问题的解具有相同的子结构。
• 解决：如果上一步分解得到的子问题可以解决，则解决这些子问题，否则，对每个子问题使用和上一步相同的方法再次分解，然后求解分解后的子问题，这个过程可能是一个递归的过程。
• 合并：将上一步解决的各个子问题的解通过某种规则合并起来，得到原问题的解。

分治法的实现模式可以是递归方式，也可以是非递归方式，一般采用递归方式的算法模式可以用伪代码描述为：

T DivideAndConquer(P)
{
    if(P 可以直接解决)
    {
        T <- P 的结果;
        return T;
    }

    将 P 分解为子问题{P1, P2,..., Pn};
    for_each(Pi : {P1, P2,..., Pn})
    {
        ti <- DivideAndConquer(Pi); //递归解决子问题 Pi
    }
    T <- Merge(t1, t2,...,tn); //合并子问题的解

    return T;
}

[快速排序](https://github.com/CyC2018/CS-Notes/blob/master/docs/notes/算法 - 排序.md#快速排序)

// qsort.cpp : Defines the entry point for the console application.
//

#include<iostream>
using namespace std;

void exchange(int *arElem, int m, int n)
{
  int tmp = arElem[m];
  arElem[m] = arElem[n];
  arElem[n] = tmp;
}

int partion(int *arElem, int p, int r) // 划分
{
  int x = arElem[r];
  int i = p;	// 区间首元素
  for(int j = p; j < r; j++)	// 遍历区间 [p, r)
  {
    if(arElem[j] < x)
    {
      if(i != j)
      {
        exchange(arElem, i, j);
      }
      i++;
    }
  }
  exchange(arElem, i, r);
  return i;  // 返回哨兵位
}

void quick_sort(int *arElem, int p, int r)
{
  if(p < r)
  {
    int mid = partion(arElem, p, r);
    quick_sort(arElem, p, mid - 1);
    quick_sort(arElem, mid + 1, r);
  }
}

void Quick_Sort(int *arElem, int n)
{
  quick_sort(arElem, 0, n - 1);
}


int main(int argc, char* argv[])
{
	int intArray[] = {12, 56, 22, 78, 102, 6, 90, 57, 29};
	Quick_Sort(intArray, 9);
	for(int i = 0; i < 9; i++)
		cout << intArray[i] << " ";

	return 0;
}

字符串全排列问题

分治法分解子问题，并不是一定要用某种方式均匀分解原始问题，哪怕是每次只能将原始问题的规模变小一点，也是一种分解子问题的方法。

对字符串类问题分解子问题，通常考虑的方法有两个。

• 一个方法是用字符串的开始位置和字符串的长度表示一个子字符串，对于一个长度为 n 的字符串，用这种方法定义的子问题就是“从位置 i 开始，长度为 m 的字符串，其中，0<m⩽n0<m⩽n”，原始问题就是从位置 1 开始，长度为 n 的字符串。
• 另一个方法是用字符串的位置区间来表示一个子字符串，同样对于一个长度为 n 的字符串，用这种方法定义的子问题就是“从位置 i 开始，到位置 j 结束的字符串，其中，1⩽i<n,i⩽j⩽n1⩽i<n,i⩽j⩽n，原始问题就是从位置 1 开始到位置 n 结束的字符串。考虑到很多编程语言中索引位置都是从 0 开始，上述描述中的索引位置要做 -1 修正，读者应该能够理解，接下来的例子用 C++ 实现算法，就会体现这一点。

我们的问题是：给定一个没有重复字母的字符串，输出该字符串中字符的所有排列。假如给定的字符串是“abc”，则应该输出“abc”、“acb”、“bac”、“bca”、“cab”和“cba”六种结果。首先分析这是一个全排列问题，解决这个问题我们的常用策略是每次选择固定一个字符，然后对剩下的两个字符进行排列。比如这个三个字母的字符串，我们首先选择固定 a，然后对 bc 进行排列，可以得到“abc”和“acb”两个结果；然后选择固定 b，对 ac 进行排列，可以得到“bac”和“bca”两个结果；最后选择固定 c，对 ab 排列，可以得到“cab”和“cba”两个结果。

我们采用的方法是将问题区间 [begin, end] 中的 begin 位置作为选中的固定字符位置，将除了这个位置之外的问题区间 [begin+1, end] 作为子问题进一步处理。如果被选中的固定字符不在 begin 位置，则交换两个字符的位置，使得被选中的固定字符位于 begin 位置。

因为我们处理方式是从前向后，每次固定 begin 位置的字符，然后将区间 [begin+1, end] 作为子问题进一步处理，所以当 begin 位置和 end 位置相同的时候，就说明字符串只有一个字符了，这时就不需要再分解子问题了。因为这个问题的特点，它不需要显式求解子问题，只需在子问题变成只有一个字符的字符串时输出这个字符串即可，并且因为之前分解子问题的时候，每个位置都已经固定好字符，所以当 begin 位置和 end 位置相同的时候，就实际得到了一个全排列结果。

#include <iostream>
#include <string>

void Swap(std::string& chList, int pos1, int pos2)
{
    if (pos1 != pos2)
    {
        char tmp = chList[pos1];
        chList[pos1] = chList[pos2];
        chList[pos2] = tmp;
    }
}

//将字符串[begin, end]区间的子串全排列
void Permutation(std::string& chList, int begin, int end)
{
    if (begin == end)
    {
        std::cout << chList << std::endl;
    }

    for (int i = begin; i <= end; i++)
    {
        Swap(chList, begin, i); //把第i个字符换到begin位置，将begin+1位置看作新的子串
        Permutation(chList, begin + 1, end); //求解子问题
        Swap(chList, begin, i); //换回来
    }
}

int main()
{
    std::string cl = "abcd";
    Permutation(cl, 0, cl.length() - 1);

    return 0;
}