序言
数组的全排列可用于求解八皇后问题。与此同时，全排列经常会出现在笔试或者面试，如求字符串的全排列。
一 全排列的递归实现
1.1 解题思路
函数Perm(int list[],int k,int m)
1.list数组
2.k前缀的索引位置，比如以12为前缀，则k=1
3.m要排列的数目，比如1为前缀，则要排列的数目为2，即m=2
给定一个n个元素数组，其全排列的过程可以描述如下：
- 1.求将list的第0k-1个元素作为前缀、第km个元素进行全排列得到的全排列。
- 2.如果k为0，且m为n，就可以求得一个数组中所有元素的全排列。
实例代码
- 核心代码
static int sum = 0; // 全排列个数
// 递归实现数组全排列
// prefixIndex - 表示前缀的位置
// number - 要排列的数目
- (void)permutation:(NSMutableArray *)arrayM prefixIndex:(int)prefixIndex number:(int)number {
if (prefixIndex == number - 1) { // 前缀是最后一个位置,此时打印排列数
// 打印数组结果
sum += 1;
[self print:arrayM len:number index:sum];
} else {
for (int i = prefixIndex; i < number; i++) {
// 交换前缀,使之产生下一个前缀. i 递增,所以可以保证数组中的每一个元素都位于第0个,作为前缀的起始字符
[self swap:arrayM i:prefixIndex j:i];
// 以递归的方式对剩下的元素进行全排列
[self permutation:arrayM prefixIndex:prefixIndex + 1 number:number];
// 将前缀换回来,继续做上一个的前缀排列.
[self swap:arrayM i:prefixIndex j:i];
}
}
}
- 辅助方法
// 实现两数交换
- (void)swap:(NSMutableArray *)arrM i:(NSUInteger)i j:(NSUInteger)j {
NSNumber *temp = arrM[i];
arrM[i] = arrM[j];
arrM[j] = temp;
}
// 打印数组内容
- (void)print:(NSMutableArray *)arrM len:(NSUInteger)len index:(int)index {
NSMutableString *strM = [NSMutableString string];
for (NSUInteger i = 0; i < len; i++) {
[strM appendString:[NSString stringWithFormat:@"%@ ",arrM[i]]];
}
NSLog(@"index:[%d] %@",index,strM);
}
- 外界调用
NSMutableArray *arrM = [NSMutableArray arrayWithObjects:@1,@2,@3, nil];
[self permutation:arrM prefixIndex:0 number:(int)arrM.count];
打印结果
image.png
1.其想法是将第k个元素与后面的每个元素进行交换，求出其全排列。这种算法比较节省空间。
2.循环将数组中所有元素与第一个元素交换时，再对子数组进行全排列后，需要将第一个元素交换回来，以供下一个元素与第一个元素交换。
1.2 考虑数组元素中有重复的元素
还是以数组{1,2,3}为例，如果数组中有重复的元素，变成了{1,2,2}，那么它的全排列就不能完全按照上面的方法求解，需要做稍微的改动。
因为全排列是将不同元素依次换到当前位置后，再对后面的元素求全排列。如果将重复的元素多次换到当前位置的话，那么就会出现相同的排列。为了避免，我们禁止将相同的元素多次换到当前位置即可。
例如，对{1，2，2}，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则
去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。
修改后代码
- 核心代码
// 递归实现数组全排列
// prefixIndex - 表示前缀的位置
// number - 要排列的数目
- (void)permutation:(NSMutableArray *)arrayM prefixIndex:(int)prefixIndex number:(int)number {
if (prefixIndex == number - 1) { // 前缀是最后一个位置,此时打印排列数
// 打印数组结果
sum += 1;
[self print:arrayM len:number index:sum];
} else {
for (int i = prefixIndex; i < number; i++) {
if ([self isSwap:arrayM len:number index:i]) {
// 交换前缀,使之产生下一个前缀. - i 递增,所以可以保证数组中的每一个元素都位于第0个,作为前缀的起始字符
[self swap:arrayM i:prefixIndex j:i];
// 以递归的方式对剩下的元素进行全排列
[self permutation:arrayM prefixIndex:prefixIndex + 1 number:number];
// 将前缀换回来,继续做上一个的前缀排列.
[self swap:arrayM i:prefixIndex j:i];
}
}
}
}
// 是否交换
- (bool)isSwap:(NSMutableArray *)arrM len:(int)len index:(int)index {
for (int i = index + 1; i < len; i++) {
if ([arrM[index] intValue] == [arrM[i] intValue]) {
return NO;
}
}
return YES;
}
- 外界传值调用
NSMutableArray *arrM = [NSMutableArray arrayWithObjects:@1,@2,@2, nil];
[self permutation:arrM prefixIndex:0 number:(int)arrM.count];
打印结果
image.png
本文参考
数组的全排列
百度百科链接 - 全排列
