为什么我用于生成排列的回溯函数永远不会停止？

Question

我尝试使用回溯编写以下函数来生成前 n 个自然数的所有排列。问题是它会遍历每个级别的每个数字，然后再确定我的 for 循环中的最后一个数字，而不管任何限制。更明确地说，它无限循环以下输出：

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

如果我删除以下约束：

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

程序打印：

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

这显然是不正确的...

我使用了我的大学提供的以下基本回溯算法来编写我的函数：

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

我不确定应该如何修复它，但我怀疑它与我的 c 变量有关。它应该指示已经选择的元素是否可以属于解决方案。

我不需要任何其他解决方案来解决排列问题，因为我确实可以访问解决方案。我只是想知道我的 reasoning/coding 出了什么问题，因为我做这个练习是为了理解回溯。

#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

好的，我解决了。主要问题是我有一个 for 循环在另一个已经做了同样事情的 do/while 循环中选择我的下一个元素。这就是函数遍历所有可能值的原因。

我摆脱了 for 循环，我消除了一些其他冗余，这里是非递归回溯排列生成器的工作代码：

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

为什么我用于生成排列的回溯函数永远不会停止？

Why does my backtracking function for generating permutations never stop?

c

algorithm

permutation

infinite-loop

backtracking