C语言，排列组合算法

一、全排列

不排序一般做法 递归法：

#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);
        }
    }
    
}