本文主要是介绍分治法实现全排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//分治法实现全排列//我们将使用分治法实现一个全排列算法。先来看一下算法实现后的效果：
//['a','b','c'].
//permutation
//["a", "b", "c"],
//["a", "c", "b"],
//["b", "a", "c"],
//["b", "c", "a"],
//["c", "b", "a"],
//["c", "a", "b"]。
//注意最后两项，我先以为可以用next_permutation实现的，后来发现分治法求出的排序和next_permutation并不一样。
//算法描述
//分治法求解问题分为三个步骤：
//- 分解：将问题分为若干个子问题。
//- 解决：递归地求解每个子问题。
//- 合并：将每个子问题的解合并成为整个问题的解。
//现在我们需要求具有n个元素的数组A的全排列。例如：大小为3的数组A=[a,b,c] (为方便起见，我把引号全都省略了，其实应该是A=['a','b','c']。下同），它的全排列为：
//[[a,b,c],
//[a,c,b],
//[b,a,c],
//[b,c,a],
//[c,a,b],
//[c,b,a]]
//这是一个大小为 n!*n 的二维数组。
//使用分治算法求解全排列的过程如下
//- 分解：将数组分为子数组 A[1..k-1] 和一个元素 A[k]。 (1≤k≤n)
//- 解决：递归地求解每个子数组 A[1..k-1] 的全排列，直至子数组A[1..k-1]为空时结束递归。
//- 合并：将上一步的结果—A[1..k-1]的全排列（一个二维数组）与元素A[k]合并，得出A[1..k]的全排列。例如：
//[[]] 与 a 合并得到 [[a]]
//[[a]] 与 b 合并得到 [[a,b], [b,a]]
//[[a,b],[b,a]] 与 c 合并得到 [[a,b,c],[a,c,b],[c,a,b],[b,c,a],[c,a,b],[c,b,a]]
//看下面的图示会更直观一些
//1. 分解过程
//[a,b,c]
/// \
//[a,b] c
/// \
//[a] b
/// \
//[] a
//2. 合并过程
//[] a
//\ /
//[[a]] b
//\ /
//[[a,b],[b,a]] c
//\ /
//[[a,b,c],
//[a,c,b],
//[c,a,b],
//[b,a,c],
//[b,c,a],
//[c,b,a]]
//对第一个元素进行局部定解
// void Perm(char *str, int n)
// {
// for(int i=0;i<n;i++)
// {
// swap(str[0],str[i]);
// Perm(str+1,n-1);
// swap(str[0],str[i]);
// }
// }
//对任意元素局部定解
//void Perm(char *str, int k, int m)
//{
// int i;
// if(k >= m) //输出 结果
// {
// for(i=1; i<=m; ++i)
// cout<<str[i]<<" ";
// cout<<endl;
// return;
// }
//
// for(i=k; i<=m; ++i) //对第k个元素局部定解，定解之后交换
// {
// Swap(str[k], str[i]);
// Perm(str, k+1, m);
// Swap(str[k], str[i]);
// }
//
//}
#include <cstring>
#include<stdio.h>
#include <iostream>
using namespace std;
#define N 4
char str[10];
void Perm(char *str, int k, int m);
void Swap(char &a, char &b); //交换顺序
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i=0; i<=n; ++i)
{
str[i] = i+'0'; //将数字1-n转化为字符型
}
Perm(str, 1, n); // 调用函数排序
}
return 0;
}
void Perm(char *str, int k, int m)
{
int i;
if(k == m) //输出
{
for(i=1; i<=m; ++i)
cout<<str[i]<<" ";
cout<<endl;
return;
}
for(i=k; i<=m; ++i) //对第k个元素局部定解，定解之后交换
{
Swap(str[k], str[i]);
Perm(str, k+1, m);
Swap(str[k], str[i]);
}
}
void Swap(char &a, char &b)
{
char tmp = a;
a = b;
b = tmp;
}
这篇关于分治法实现全排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
