Why does my backtracking function for generating permutations never stop?

Question

I tried writing the following function using backtracking to generate all permutations of the first n natural numbers. The problem is that it goes thorugh every number on each level before settling for the last number in my for loop, regardless of any constraints. More explicitly, it infinitely loops the following output:

We pick 1 on level 0
We pick 2 on level 0
We pick 3 on level 0
We pick 1 on level 1
We pick 2 on level 1
We pick 3 on level 1

If I remove the following constraints:

for(j=0; j<k; j++) if(v[j]==v[k]) c=0;

The program prints:

We pick 1 on level 0
We pick 2 on level 0
We pick 3 on level 0
We pick 1 on level 1
We pick 2 on level 1
We pick 3 on level 1
We pick 1 on level 2
We pick 2 on level 2
We pick 3 on level 2
333

Which is clearly not correct...

I used the following base backtracking algorithm provided by my university for writing my function:

k = 0;
while (k >= 0)
{
    do
    {
        * pick next x[k] out of the S[k] set
        * evaluate Continue(x[1], x[2], ..., x[k])
    }
    while ( !Continue(x[1], x[2], ..., x[k]) &&
            (* there are still elements to pick out of the S[k] set) )
    if (Continue(x[1], x[2], ..., x[k]))
    {
        if (k == n-1)
        {
            if (Solution(x[1], x[2], ..., x[n]))
                * print solution
        }
        else
        {
            k = k + 1;
        }
    }
    else
    {
        k = k - 1;
    }
}

I am not sure how I am supposed to fix it, but I suspect it has something to do with my c variable. It is supposed to indicate whether the already selected elements can ever belong to a solution.

I do not want any other solutions for solving the permutations problem, as I do have access to a solution. I merely want to know what is wrong with my reasoning/coding since I was doing this exercise to understand backtracking.

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

int main()
{
    int i, j, c, n, *x, k=0;
    int v[3];
    printf("Introduce n: "); scanf("%d",&n);
    x=(int*)malloc(n*sizeof(int));
    for(i=0; i<n; i++)
    x[i]=1;
    while (k >= 0)
    {
        do
        {
            // pick next x[k] out of the S[k] set
            for(i=x[k]; i<=n; i++)
            {
            printf("We pick %d on level %d\n", i, k);
            getchar();
            c=1;
            v[k]=i;
            x[k]++;
            if(x[k]>n)
                {x[k]=1;}
            // We evaluate Continue(x[1], x[2], ..., x[k])
            for(j=0; j<k; j++)
                if(v[j]==v[k])
                {
                    c=0;
                }
            }
        }
        while((c==0)&&(v[k]<n));

        if (c==1)
        {
            if(k==n-1)
            {
                k=k-1;
                // printing solution
                for(i=0; i<n; i++)
                printf("%d",v[i]);
                printf("\n");
             }
            else
            {
                k=k+1;
            }
        }
        else
        {
            k=k-1;
        }
    }
    return 0;
}

Answer 1

Okay, I solved it. The main problem was that I had a for loop pick my next element inside another do/while loop that already did the same thing. This is why the function looped through all possible values.

I got rid of the for loop, I eliminated some other redundancies and here is the working code of the non-recursive backtracking permutations generator:

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

int main()
{
    int i, c, n, *v, k=0;
    printf("Introduce n: "); scanf("%d",&n);
    v=(int*)calloc(n,sizeof(int));
    while (k >= 0)
    {
        do
        {
            // pick next x[k] out of the S[k] set
            v[k]++;
         //   printf("We pick %d on level %d\n", v[k], k);
          //  getchar();
            // We evaluate Continue(x[1], x[2], ..., x[k])
            c=1;
            if(v[k]>n)
            {
                c=0;
                break;
            }
            for(i=0; i<k; i++)
                if(v[i]==v[k])
                {
                    c=0;
                    break;
                }
        }
        while((c==0)&&(v[k]<n));

        if (c==1)
        {
            if(k==n-1)
            {
                // printing solution
                for(i=0; i<n; i++)
                printf("%d",v[i]);
                printf("\n");
                v[k]=0;
                k=k-1;
             }
            else
            {
                k=k+1;
            }
        }
        else
        {
            v[k]=0;
            k=k-1;
        }
    }
    return 0;
}