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

我想生成所有可能的从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;
}

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

最佳答案

我用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
一种方法是在subk函数中将最后一个数字（index == (k - 1)）写入缓冲区时，只执行一次for循环。
为了实现这一点，您需要在for循环的末尾添加以下两行。

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

（您也可以使用return代替break）
添加这两行后，函数应如下所示：

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行移到函数的开头，并将if语句中的s[index] = prev;更改为k。
现在函数应该如下所示：

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

使用此解决方案，当k - 1显示程序位于最后一个“子编号”时，永远不会执行for循环。它只是显示数字并退出函数，因为返回。
这两个解决方案都能得到正确的结果，但我个人更喜欢第二个解决方案，因为for循环的每次迭代都没有执行额外的if语句，而且程序（稍微）更快。

关于c - 从n个长度为k的数中生成递增的子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47120273/