c - C中递归函数枚举并返回二维数组n选k的所有组合

Question

我正在使用递归函数(来自此处的一篇文章)来枚举从 n 中选择 k 项的所有组合。我修改了这个函数以保存和返回二维数组中的枚举组合(作为 arrPtr 传递给函数)。我在 for 循环(来自 main)中针对不同的 k 值(k 从 1 到 n-1)调用这个递归函数，以生成 n 和 k 的任何值的所有组合。现在，'count' 被定义为静态整数，函数生成 k=1 的所有组合，然后转到 k=2，但随后在某一点停止。原因是我使用变量“count”作为 arrPtr 中行的索引。由于它是一个静态变量，因此在其他轮次(k=2、3、4 等)调用该函数时，它不会重置为 0。因此，它会在某个点之后导致 arrPtr 的访问冲突。当我为'count'删除'static'时，它会生成不同k值的所有组合，但只有每轮中的最后一个组合保存在arrPtr中(同样是由于删除'static')。如何在 arrPtr 中连续保存每个生成的组合，以便我可以获得(并返回)最后保存在 arrPtr 指向的一个位置的所有组合？

我尝试使用引用传递(传递变量的地址)将 arrPtr 中行的索引传递给函数，但是当递归函数调用自身时，这会遇到麻烦。我搜索了很多并在这里找到了类似的主题(例如，从递归函数返回数组)，但它们主要针对其他编程语言(我只使用 C；甚至不使用 C++)。我花了很多时间来解决这个问题，现在真的需要帮助。先感谢您。

int** nCk(int n,int loopno,int ini,int *a,int **arrPtr, int k)
{
static int count=0;

int total; // equal to the total number of combinations of nCk
int i,j;

total = factorial(n)/(factorial(n-k)*factorial(k)); 

loopno--;
if(loopno<0)
{
    a[k-1]=ini;

    for(j=0;j<k;j++)
    {
    printf("%d,",a[j]);
    arrPtr[count][j]=a[j];
    }
    printf("count =%d\n",count);

    count++;

    return 0;
}

for(i=ini;i<=n-loopno-1;i++)
{
    a[k-1-loopno]=i+1;
    nCk(n,loopno,i+1,a,arrPtr,k);
}

if(ini==0)

return arrPtr; // arrPtr is in fact an array of pointers, where each pointer points to an array of size k (one of the combinations of selecting k out of n elements

else
return 0;
}

Answer 1

我的理解是

你想计算 nCk 中 n 和 k 的任意值的组合，

在外部定义一个 factorial() 函数并且定义一个 combi() 函数...计算 n 和 k 变量的组合值

两者都在定义 main() 函数之前起作用...这样您就可以避免先声明再定义(我的意思是避免额外的代码行)。

这里是 combi() 函数的代码

function combi(int n , int k){
int nFact, kFact, n_kFact, p;
int comb;
nFact=factorial(n);
kFact=factorial(k);
p=n-k;
n_kFact=factorial(p);
comb= nFact / ((n_kFact) * kFact);
return comb;
}

你可以在你的主函数中调用这个函数....使用for循环来存储相对n和k的组合值....这样你就会得到你需要的....也可以传递指针或

&array[0][0]

即数组的起始地址...以便您可以在程序的任何位置访问该数组。

希望对您有所帮助。谢谢