c - 回溯算法生成所有组合

Question

我对此有一个小问题。我想生成所有可能的组合。数字位于一维数组中，它是从文件中读取的。现在我不知道问题所在:我知道将打印到监视器的每个组合都是按升序排列的。问题是，如果它以最小的数字结束，它不会上升到下一个数字。

示例:1、2、3、4、5 且 n = 5、p = 3 的一维数组文件；可能的组合:

1 2 3，1 2 4,1 2 5,1 3 4,1 3 5,1 4 5,2 3 4,2 3 5,等等...

这是我到目前为止所做的:

#include <stdio.h>
#include <stdlib.h>

void print(int*,int);
void combination(int*,int,int,int);
int main()
{
    FILE *fin = fopen("bemenet.txt","r");
    if(!fin){printf("Error opening file @!!!");return 0;}
    int *a,i,n,p = 3;
    fscanf(fin,"%i ",&n);
    a = (int*)malloc(n*sizeof(int));
    for(i = 0; i < n; ++i){
        fscanf(fin,"%i ",&a[i]);
    }
    combination(a,n,p,0);

    return 0;
}

void combination(int *a,int n,int p,int k)
{
    int i;
    if(k == p){
        print(a,k);
    }
    else{
        for(a[k + 1] = a[k] + 1 ; a[k+1] < n; ++a[k+1]){
            combination(a,n,p,k+1);
        }
    }
}
void print(int *a,int k)
{
    int i;
    for(i = 0; i < k; ++i){
        printf("%i ",a[i]);
    }
    printf("\n");
}

Answer 1

数字仅递增的原因是，您永远不会递减它们。还有条件a[k+1] < n对我来说没有任何意义，为什么要将字段的大小与数组的元素(可以是例如 1000)进行比较？另外，您不应该将数组中的元素更改为 ++a[k+1]因为没有理由这样做。

参见示例 Algorithm to generate all possible permutations of a list?以获得更多帮助。