首页 > 代码库 > 字符串数组的全排列——数组
字符串数组的全排列——数组
题目描写叙述：
输入一个字符串，打印出该字符串中字符的全部排列。
解题思路：
參考july大神的编程艺术系列.使用字典排序。求当前排列的下一个字典序列。即全排列的下一个排列.
所谓字典序列，即给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔集 A × B。则字典序定义为
(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′)。
所以给定两个字符串。逐个字符比較，那么先出现较小字符的那个串字典顺序小。假设字符一直相等。较短的串字典顺序小。
比如：abc < abcd < abde < afab。
起点： 字典序最小的排列, 1-n , 比如12345
终点： 字典序最大的排列。n-1, 比如54321
过程： 从当前排列生成字典序刚好比它大的下一个排列
next_permutation算法
定义
升序：相邻两个位置ai < ai+1，ai 称作该升序的首位
步骤（二找、一交换、一翻转）
- 找到排列中最后（最右）一个升序的首位位置i，x = ai
- 找到排列中第i位右边最后一个比ai 大的位置j。y = aj
- 交换x，y
- 把第(i+ 1)位到最后的部分翻转
- x = 1。
- y = 3
- 1和3交换
- 得23541
- 翻转541
- 得23145
參考代码：
<span style="font-size:18px;">class Solution{
public:
void calcAllpermutaion(char *perm, int from, int to)
{
if (to <= 1)
return;
if (from == to)
{
for (int i = 0; i <= to; i++)
cout << perm[i];
cout << endl;
}
else
{
for (int j = from; j <= to; j++)
{
swap(perm[j], perm[from]);
calcAllpermutaion(perm, from + 1, to);
swap(perm[j], perm[from]);
}
}
}
bool calcNextPermutation(char *perm, int len){
int i = 0, j = 0;
for (i = len - 2; (i >= 0) && (perm[i] >= perm[i + 1]); i--);
if (i < 0)
return false;
for (j = len - 1; (j>i) && (perm[j] <= perm[i]); j--);
swap(perm[i], perm[j]);
reverse(perm + i + 1, perm + len - 1);
return true;
}
};</span>參考：http://taop.marchtea.com/01.06.html
字符串数组的全排列——数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。