问题1、求长度为N的字符串的所有排列，如字符串abc所有排列为：abc,acb,bac,bca,cab,cba。
问题2、求长度为N的字符串的所有组合，注意是组合，不是排列，
如“abc”所有组合为：a、b、c；ab、ac、bc；abc。
注意：ab和ba是一个组合，abc和acb、bca、cab等是一个组合，其他类似；
题目很常见，网上也有很多其他语言的算法，但是iOS开发语言objective-c写的甚少，所以就结合自己理解写了一套，代码如下：
问题1：字符串排列算法
思路：
把一个字符串看成两部分组成：第一部分为第一个字符，第二部分为后面的所有字符。
所以整个字符串的排列，可以看出两步：
第一步求所有可能出现在第一个位置的字符，即把第一个字符和后面的所有字符交换；
第二步固定第一个字符，求后面所有字符的排序。
依次类推： 把后面的字符看成两部分，第一个字符和后面的字符，然后重复上述步骤。（递归）
代码如下：
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view.
NSString *str = @"abc";
[arrangementArray addObject:str];
[self arrangementStr:str begin:0];
}
/* <#注释#>
* @param string：要排列的字符串
* @param i：要交换的字符的位置：第i个字符和后面的字符交换
*/
- (void)arrangementStr:(NSString *)string begin:(int)i
{
//当前位置i和后面的字母依次交换，循环i位置后面的字母
for (int j = i + 1; j < string.length; j ++) {
/* <#注释#>
string没有交换方法，只有替换方法；所以需要取i、j上对应的字母，然后再做交换替换。
array有交换方法。
*/
NSString *tempStr = string;
NSString *temp = [tempStr substringWithRange:NSMakeRange(i, 1)];
NSString *exc = [tempStr substringWithRange:NSMakeRange(j, 1)];
//先用后面的替换当前的；再用当前的替换后面的
tempStr = [tempStr stringByReplacingCharactersInRange:NSMakeRange(i, 1) withString:exc];
tempStr = [tempStr stringByReplacingCharactersInRange:NSMakeRange(j, 1) withString:temp];
/* 内部新生成的字符串递归循环，针对新生成的非以当前字母开头的字符串进行排列 进行递归.
（如原始是abcd,开头字母是a，则此句是针对b、c、d开头的排列；二级循环：如果是bcd，则针对c、d开头进行排列，依次类推。）
如果不好理解：注释掉此句，看打印结果变化。
*/
[self arrangementStr:tempStr begin:i+1];
[arrangementArray addObject:tempStr];
NSLog(@"exchang str ---=== %@---== %ld",tempStr,arrangementArray.count);
}
/* <#注释#>
针对以当前字母开头的进行后续递归：如当前是abcd，则a不变，对bcd进行递归。
*/
if (i + 1 < string.length) {
[self arrangementStr:string begin:i + 1];
}
}
/* 排列打印结果
arrangementArray === (
abc,
bca,
bac,
cab,
cba,
acb
)
*/
问题2：字符串所有组合算法
思路：这个问题可以看成两部分：1、求从长度为N的字符串中取出
M个字符(M <= N)的所有组合；2、依次取长度为1、2、... 一直到N个字符的组合，再相加进行组合，即为长度为N的字符串所有组合。
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view.
NSString *str = @"abc";
// [arrangementArray addObject:str];
// [self arrangementStr:str begin:0];
[self getAllCombinationFromString:str];
}
//获取字符串的所有组合
- (void)getAllCombinationFromString:(NSString *)string
{
__block NSMutableArray *muArray = [NSMutableArray new];
for (int i = 1; i <= string.length; i ++) {
[self combinationNum:i fromStr:string curStr:@"" curIndex:0 curLength:1 result:^(NSString *combin) {
[muArray addObject:combin];
}];
}
NSLog(@"combinationNum array ==== %@",muArray);
}
/* <#注释#>
* @param n：所要组合的字符串长度�
* @param oriStr：原始字符串
* @param curStr：当前字符串
* @param index：当前所要添加字符在原始字符串中的index
* @param length:当前字符串长度
* @block:每次循环组合后的字符串回调
*/
- (void)combinationNum:(NSInteger)n
fromStr:(NSString *)oriStr
curStr:(NSString *)curStr
curIndex:(int)index
curLength:(NSInteger)length
result:(void (^)(NSString *combin))block
{
NSString *tempStr = curStr;
for (int i = index; i < oriStr.length + length - n; i ++) {
//如果当前长度小于要求的字符长度n
if (length <= n) {
//依次添加字符串
curStr = [curStr stringByAppendingString:[oriStr substringWithRange:NSMakeRange(i, 1)]];
[self combinationNum:n fromStr:oriStr curStr:curStr curIndex:i + 1 curLength:length + 1 result:block];
if (length == n) {
NSLog(@"out --=== %@",curStr);
block(curStr);
}
}else return;
curStr = tempStr;
}
}
/* 打印结果：
combinationNum array ==== (
a,
b,
c,
ab,
ac,
bc,
abc
)
*/
if you like,请左边👈🏻点个赞👍🏻👍🏻👍🏻支持下吧！
参考链接
排列：https://www.cnblogs.com/liang1101/p/6376210.html
组合：https://blog.csdn.net/u014039577/article/details/50353198
网友评论