分治法实现全排列

2024-09-01 17:58
文章标签 实现 分治 排列

本文主要是介绍分治法实现全排列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

//分治法实现全排列
//我们将使用分治法实现一个全排列算法。先来看一下算法实现后的效果:
//['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;
}

这篇关于分治法实现全排列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1127649

相关文章

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具