| 递归实现字符串的全排列 | 您所在的位置：网站首页 › 递归排列 › 递归实现字符串的全排列 |
递归实现字符串的全排列
|
1. 题目描述
输入一个字符串，要求输出其所有的全排列 2. 输入输出描述 输入： abc 输出： abc acb bac bca cba cab (输出个数为输入字符串长度的阶乘) 3. 算法分析 对于全排列，最直接的想法就是，交换字符串中所有情况下的两个字符，为了遍历完所有的情况，我们对循环必须有一定的规律，例如：先交换第一个字符和其后面的所有字符，然后交换第二字符与其后面的所有字符，直到倒数第二个字符与最后的一个字符的交换，该循环结束。这样一层套一层的循环，最适合的方法当然就是递归了。
4. 代码实现 C++实现： #include #include using namespace std; template void Swap(Type &a, Type&b) { Type temp = a; a = b; b = temp; } void Perm(string str, int k, int m) { if (k == m - 1) { cout str; Perm(str, 0, str.length()); return 0; } Python实现： string = input() def Swap(string, i, j): """ 交换字符串string中的第i个元素和第j个元素 """ string = list(string) temp = string[i] string[i] = string[j] string[j] = temp string = "".join(string) return string def Perm(string, k, m): """ 依次循环交换 最外层：第一位数与其后面的各位数进行交换 次外层：第二位数与其后面的各位数进行交换 一直循环... 最后一层：倒数第二位与倒数第一位进行交换 """ if(k == m-1): print(string) else: for i in range(k, m): string = Swap(string, k, i) Perm(string, k+1, m) string = Swap(string, k, i) Perm(string, 0, len(string)) 5. 测试结果：
|
【本文地址】
公司简介
联系我们