从长度为 k 的 n 个数中生成递增子序列

Question

我想生成从 1 到 n，但长度为 k 的所有可能的递增数字子序列（允许重复）。
前任。 n=3, k=2
输出：

这是我的代码：

#include <stdio.h>

int s[100];
int n=6;
int k=4;

void subk(int prev,int index)
{
    int i;
    if (index==k)
    {
        for(int i=0; i<k; i++)
            printf("%d ",s[i]);

        printf("\n");
        return;
    }
    s[index]=prev;
    for (i=prev; i<=n; ++i)
    {
        subk(i,index+1);//,s,n,k);
    }

}
int main()
{
    int j;
    for (j = 1; j<=n ; ++j)
    {
        subk(j,0);
    }
    return 0;
}

但这会产生一些不需要的重复。我该如何消除这些？

Answer 1

我已经用 n = 3 和 k = 2 测试了您的代码并得到以下结果：

这显然是不正确的，因为有几个相同的数字，例如 1 1 或 1 2。

但到底哪里出了问题？
如果 n = 3 和 k = 3，让我们写下正确的结果。现在将这些与我们在 n = 3 和 k = 2.

时从程序中得到的结果进行比较

    correct      program (incorrect)
    k = 3        k = 2
    1 1 1        1 1     
    1 1 2        1 1     
    1 1 3        1 1     
    1 2 2        1 2     
    1 2 3        1 2     
    1 3 3        1 3     
    2 2 2        2 2     
    2 2 3        2 2     
    2 3 3        2 3     
    3 3 3        3 3

现在我们可以看到程序的错误输出与我们设置k = 3时正确答案的前两列相同。这意味着如果我们设置 k = 2，程序解决了 3 列的问题，但只显示前两列。

您需要阻止程序多次写入相同的数字。

解决方案 1

一种方法是在将最后一个数字 (index == (k - 1)) 写入缓冲区 s 时，仅在 subk 函数中执行一次 for 循环。为了实现这一点，您需要将以下两行添加到您的 for 循环的末尾。

if (index == (k - 1))
    break;

（代替 break 你也可以使用 return）

添加这两行后，函数应如下所示：

void subk(int prev, int index)
{
    int i;
    if (index == k)
    {
        for (int i = 0; i<k; i++)
            printf("%d ", s[i]);

        printf("\n");
        return;
    }
    s[index] = prev;
    for (i = prev; i <= n; ++i)
    {
        subk(i, index + 1);//,s,n,k);
        if (index + 1 == k)
            break;
    }

}

解决方案 2

另一种解决问题的方法是将行 s[index] = prev; 移动到函数的开头，并将 if 语句中的 k 更改为 k - 1.
现在该函数应如下所示：

void subk(int prev, int index)
{
    int i;
    s[index] = prev;

    if (index == k - 1)
    {
        for (int i = 0; i<k; i++)
            printf("%d ", s[i]);

        printf("\n");
        return;
    }

    for (i = prev; i <= n; ++i)
    {
        subk(i, index + 1);//,s,n,k);
    }
}

使用此解决方案，当 index 显示程序在最后 'sub-number' 时，永远不会执行 for 循环。由于 return.

，它只显示数字并退出函数

两种解决方案都能得到正确的结果，但我个人更喜欢第二种解决方案，因为没有额外的 if 语句在 for 循环的每次迭代中执行，而且程序（稍微）更快。

从长度为 k 的 n 个数中生成递增子序列

Generating increasing subsequences out of n numbers of length k

c

arrays

recursion

loops

subsequence

解决方案 1

解决方案 2