CODEWITHSUNDEEP
carraysloopsrecursionsubsequence
Vijayraj S
Vijayraj S

Reputation: 81

Generating increasing subsequences out of n numbers of length k

I want to generate all possible increasing subsequences of numbers (repetition allowed) from 1 to n, but of length k.
Ex. n=3, k=2
Output: 

1 1
1 2
1 3
2 2
2 3
3 3

This is my code:

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

But this generates some unwanted repetitions. How do I eliminate those?

Upvotes: 1

Views: 142

Answers (1)

Glordir
Glordir

Reputation: 36

I have tested your code with n = 3 and k = 2 and got the following result:

1 1
1 1
1 1
1 2
1 2
1 3
2 2
2 2
2 3
3 3

This is obviously incorrect, as there are several identical numbers like 1 1 or 1 2.

But what exactly went wrong?
Let's write down the right results if n = 3 and k = 3. Now compare those to the result we got from the program when n = 3 and 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

Now we can see that the incorrect output of the program is the same as the first two columns of the correct answer when we set k = 3. This means that the program solves the problem for 3 columns if we set k = 2, but only displays the first two columns.

You need to stop the program from writing the same number several times.

Solution 1

One way to do this is to execute the for-loop in the subk-function only once when it writes the last number (index == (k - 1)) into the buffer s. In order to achieve this, you need to add the following two lines to the end of your for-loop.

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

(Instead of the break you could also use return)

After you added these two lines the function should look like this:

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

}

Solution 2

Another way to solve the problem is to move the line s[index] = prev; to the beginning of the function and change the k in the if-statement to k - 1.
Now the function should look like this: 

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

With this solution, the for-loop is never executed when the index shows that the program is at the last 'sub-number'. It just displays the number and exits the function because of the return.

You get the right result with both solutions, but I personally like the second solution better, because there is no additional if-statement that is executed every iteration of the for-loop and the program is (slightly) faster.

Upvotes: 2

Related Questions