一、全排列
不排序一般做法 递归法：
#include <stdio.h>
#include <stdlib.h>
//递归
void traverse(int *a, int index, int num);
//交换
void swap(int *a, int *b);
int main(int argc, char *argv[])
{
//获取输入数字
int num = 0;
scanf("%d", &num);
printf("%d\n", num);
//初始化
int a[num];
for(int i=0; i<num; i++) {
a[i] = i+1;
}
//递归调用
traverse(a, 0, num);
}
void traverse(int *a, int index, int num)
{
if (index == num) {
//最后遍历输出
for(int i=0; i<num; i++) {
printf("%d", a[i]);
}
printf("\n");
} else {
for(int i=index; i<num; i++) {
//当前位的数，和后续几位，逐一替换
swap(&a[i], &a[index]);
traverse(a, index+1, num);
//再次替换，相当于撤销替换
swap(&a[i], &a[index]);
}
}
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
输入：3
输出：
123
132
213
231
321
312
参考图片：
image.png
排序做法：(假设从小到大排)
针对排序的核心思想：在第一交换后，递归前，将从index往后的数据，进行从小到大排序，
如上图： 当123交换成 321的时候，将321转换成312，保持除第一位3之后的另外两位的有序，
#include <stdio.h>
#include <stdlib.h>
//递归
void traverse(int *a, int index, int num);
//交换
void swap(int *a, int *b);
int main(int argc, char *argv[])
{
//获取输入数字
int num = 0;
scanf("%d", &num);
printf("%d\n", num);
//初始化
int a[num];
for(int i=0; i<num; i++) {
a[i] = i+1;
}
//递归调用
traverse(a, 0, num);
}
void traverse(int *a, int index, int num)
{
if (index == num) {
//最后遍历输出
for(int i=0; i<num; i++) {
printf("%d", a[i]);
}
printf("\n");
} else {
for(int i=index; i<num; i++) {
//当前
swap(&a[i], &a[index]);
//从index后，数据要排序 ，这对从小到大排序 针对递增
int temp[num]; //为了方便递归后的撤销，这里申请变量
for(int i=0; i<num; i++) {
temp[i] = arr[i];
}
for(int m=index+1; m<num-1; m++) {
for(int n=m+1; n<num; n++) {
if (temp[m] > temp[n]) {
swap(&temp[m], &temp[n]);
}
}
}
reverse(temp, index+1, num);
//撤销替换
swap(&a[i], &a[index]);
}
}
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
输入：3
输出：
123
132
213
231
312
321
二、包含重复数据的排列组合
在普通排列组合的基础之上，从第一个数字起，每个数与它后面非重复出现的数进行交换。
用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。
#include <stdio.h>
#include <stdlib.h>
void reverse(int *arr, int index, int num);
void swap(int *a, int *b);
int main(int argc, char *argv[])
{
//处理输入参数
int num = 0;
scanf("%d", &num);
int arr[2*num];
for(int i=0; i<num; i++) {
arr[2*i] = i+1;
arr[2*i+1] = i+1;
}
reverse(arr, 0, 2*num);
}
void reverse(int *arr, int index, int num)
{
if (index == num) {
for(int i=0; i<num; i++) {
printf("%d ", arr[i]);
}
printf("\n");
} else {
for(int i=index; i<num; i++) {
// 是否可以交换 0否 1是
int isChange = 1;
//如果是开始
if (i!=index) {
//i=index，是可以进行交换的
//判断[index,i)之间是否有跟arr[i]重复的数,有则不进行交换
for(int m=index; m<i; m++) {
if (arr[m] == arr[i]) {
isChange = 0;
m = i;
}
}
}
if (isChange) {
swap(&arr[i], &arr[index]);
reverse(arr, index+1, num);
swap(&arr[i], &arr[index]);
}
}
}
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
二、组合
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
* arr 待组合数据
* res 组合结果保存数据
* index 当前要写入结果的key
* start 当前递归开始位置
* max arr最大长度
* num 当前尚需组合的个数
* len 组合后结果的长度，方便输出
*/
void recursion(int *arr, int *res, int index, int start, int max, int num, int len);
int main(int argc, char *argv[])
{
int max = 0, num = 0;
scanf("%d %d", &max, &num);
int arr[max];
memset(arr, 0, sizeof(arr));
for(int i=0; i<max; i++) {
arr[i] = i+1;
}
//组合数据
int res[num];
memset(res, 0, sizeof(res));
recursion(arr, res, 0, 0, max, num, num);
return 0;
}
void recursion(int *arr, int *res, int index, int start, int max, int num, int len)
{
if (num == 0) {
//当待填充的个数为0时，表示结束
for(int i=0; i<len; i++) {
printf("%d ", res[i]);
}
printf("\n");
} else {
for(int i=start; i<=max-num; i++) {
//针对当前index, 遍历剩余可用的数填充递归
res[index] = arr[i];
recursion(arr, res, index+1, i+1, max, num-1, len);
}
}
}
网友评论