手写全排列(递归 | 非递归)

2024-09-05 04:08
文章标签 递归 手写 排列

本文主要是介绍手写全排列(递归 | 非递归),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

博客搬家:最爱午后红茶

以下内容转自:点击打开链接

用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列, 
如 abc 的全排列: abc, acb, bca, dac, cab, cba

一.全排列的递归实现

为方便起见,用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后,递归的代码就很容易写出来了:

//全排列的递归实现
#include <stdio.h>
#include <string.h>
void Swap(char *a, char *b)
{char t = *a;*a = *b;*b = t;
}
//k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr, int k, int m)
{if (k == m){static int s_i = 1;printf("  第%3d个排列\t%s\n", s_i++, pszStr);}else{for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列{Swap(pszStr + k, pszStr + i);AllRange(pszStr, k + 1, m);Swap(pszStr + k, pszStr + i);}}
}
void Foo(char *pszStr)
{AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{printf("         全排列的递归实现\n");printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");char szTextStr[] = "123";printf("%s的全排列如下:\n", szTextStr);Foo(szTextStr);return 0;
}

注意这样的方法没有考虑到重复数字

二.去掉重复的全排列的递归实现

由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122,第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了,但对212,它第二个数与第三个数是不相同的,交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。

换种思维,对122,第一个数1与第二个数2交换得到212,然后考虑第一个数1与第三个数2交换,此时由于第三个数等于第二个数,所以第一个数不再与第三个数交换。再考虑212,它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。

这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时,要求[i,j)中没有与第j个数相等的数。下面给出完整代码:

//去重全排列的递归实现
#include <stdio.h>
#include <string.h>
void Swap(char *a, char *b)
{char t = *a;*a = *b;*b = t;
}
//在pszStr数组中,[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等
bool IsSwap(char *pszStr, int nBegin, int nEnd)
{for (int i = nBegin; i < nEnd; i++)if (pszStr[i] == pszStr[nEnd])return false;return true;
}
//k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr, int k, int m)
{if (k == m){static int s_i = 1;printf("  第%3d个排列\t%s\n", s_i++, pszStr);}else{for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列{if (IsSwap(pszStr, k, i)){Swap(pszStr + k, pszStr + i);AllRange(pszStr, k + 1, m);Swap(pszStr + k, pszStr + i);}}}
}
void Foo(char *pszStr)
{AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{printf("         去重全排列的递归实现\n");printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");char szTextStr[] = "122";printf("%s的全排列如下:\n", szTextStr);Foo(szTextStr);return 0;
}

OK,到现在我们已经能熟练写出递归的方法了,并且考虑了字符串中的重复数据可能引发的重复数列问题。那么如何使用非递归的方法来得到全排列了?

三.全排列的非递归实现

要考虑全排列的非递归实现,先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列,全排列的也就迎刃而解了。

如何计算字符串的下一个排列了?来考虑"926520"这个字符串,我们从后向前找第一双相邻的递增数字,"20"、"52"都是非递增的,"26 "即满足要求,称前一个数字2为替换数,替换数的下标称为替换点,再从后面找一个比替换数大的最小数(这个数必然存在),0、2都不行,5可以,将5和2交换得到"956220",然后再将替换点后的字符串"6220"颠倒即得到"950226"。

对于像"4321"这种已经是最“大”的排列,采用STL中的处理方法,将字符串整个颠倒得到最“小”的排列"1234"并返回false。

这样,只要一个循环再加上计算字符串下一个排列的函数就可以轻松的实现非递归的全排列算法。按上面思路并参考STL中的实现源码,不难写成一份质量较高的代码。值得注意的是在循环前要对字符串排序下,可以自己写快速排序的代码(请参阅《白话经典算法之六 快速排序 快速搞定》),也可以直接使用VC库中的快速排序函数(请参阅《使用VC库函数中的快速排序函数》)。下面列出完整代码:

//全排列的非递归实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Swap(char *a, char *b)
{char t = *a;*a = *b;*b = t;
}
//反转区间
void Reverse(char *a, char *b)
{while (a < b)Swap(a++, b--);
}
//下一个排列
bool Next_permutation(char a[])
{char *pEnd = a + strlen(a);if (a == pEnd)return false;char *p, *q, *pFind;pEnd--;p = pEnd;while (p != a){q = p;--p;if (*p < *q) //找降序的相邻2数,前一个数即替换数{//从后向前找比替换点大的第一个数pFind = pEnd;while (*pFind <= *p)--pFind;//替换Swap(pFind, p);//替换点后的数全部反转Reverse(q, pEnd);return true;}}Reverse(p, pEnd);//如果没有下一个排列,全部反转后返回truereturn false;
}
int QsortCmp(const void *pa, const void *pb)
{return *(char*)pa - *(char*)pb;
}
int main()
{printf("         全排列的非递归实现\n");printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");char szTextStr[] = "abc";printf("%s的全排列如下:\n", szTextStr);//加上排序qsort(szTextStr, strlen(szTextStr), sizeof(szTextStr[0]), QsortCmp);int i = 1;do{printf("第%3d个排列\t%s\n", i++, szTextStr);}while (Next_permutation(szTextStr));return 0;
}

至此我们已经运用了递归与非递归的方法解决了全排列问题,总结一下就是:

1.全排列就是从第一个数字起每个数分别与它后面的数字交换。

2.去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

3.全排列的非递归就是由后向前找替换数替换点,然后由后向前找第一个比替换数大的数与替换数交换,最后颠倒替换点后的所有数据。

这篇关于手写全排列(递归 | 非递归)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

oracle11.2g递归查询(树形结构查询)

转自: 一 二 简单语法介绍 一、树型表结构:节点ID 上级ID 节点名称二、公式: select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员:SQL 递归: 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速

stl的sort和手写快排的运行效率哪个比较高?

STL的sort必然要比你自己写的快排要快,因为你自己手写一个这么复杂的sort,那就太闲了。STL的sort是尽量让复杂度维持在O(N log N)的,因此就有了各种的Hybrid sort algorithm。 题主你提到的先quicksort到一定深度之后就转为heapsort,这种是introsort。 每种STL实现使用的算法各有不同,GNU Standard C++ Lib

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E

JS手写实现深拷贝

手写深拷贝 一、通过JSON.stringify二、函数库lodash三、递归实现深拷贝基础递归升级版递归---解决环引用爆栈问题最终版递归---解决其余类型拷贝结果 一、通过JSON.stringify JSON.parse(JSON.stringify(obj))是比较常用的深拷贝方法之一 原理:利用JSON.stringify 将JavaScript对象序列化成为JSO

T1打卡——mnist手写数字识别

🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者:K同学啊 1.定义GPU import tensorflow as tfgpus=tf.config.list_physical_devices("GPU")if gpus:gpu0=gpus[0]tf.config.experimental.set_memort_groth(gpu0,True) #设置GPU现存用量按需

python 实现第k个字典排列算法

第k个字典排列算法介绍 "第k个字典排列"算法通常指的是在给定的字符集合(例如,字符串中的字符)中,找到所有可能排列的第k个排列。这个问题可以通过多种方法解决,但一个常见且高效的方法是使用“下一个排列”算法的变种,或称为“第k个排列”的直接算法。 方法一:使用“下一个排列”的变种 生成所有排列:首先生成所有排列,但显然这种方法对于较大的输入集合是不切实际的,因为它涉及到大量的计算和存储。 排序