不产生词典输出的置换器

Question

我正在研究euler项目的问题24，经过几天的研究，并且充分了解了什么是回溯以及如何实现它，我终于让我的置换器开始工作了，这里是：

//Lexicographic Permutations, Project Euler Problem 24
/*The lexicographic permutations of 0, 1 and 2 are:
012   021   102   120   201   210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? */

#include <stdio.h>
#define TARGET 1000000 

int iteration=0;

int permute(char*,int,int);
int swap(int,int);
char digits[10]="0123456789";


int main(){
    permute(digits,0,9);
}

int permute(char*digits,int start, int end){
//  printf("permute(%s, %d, %d)\n",digits,start,end);
    if (start==end){
        iteration++;
//  if ((iteration==TARGET) printf ("iteration %d: %s\n",iteration, digits);
    }else

        for (int i=start ; i<=end ; i++){
            swap (start, i);
            permute (digits, start+1, end);
            swap (start, i);
        }
    return 0;
}

int swap(int a,int b){
//  printf("swap(%d,%d)\n",a,b);
    int temp;
    temp=digits[a];
    digits[a]=digits[b];
    digits[b]=temp;
    return 0;
}

但是，对这个问题的正确答案应该是2783915460，在我的例子中，它位于迭代998580中.以下是一些示例输出：

...
2783915604 found at iteration:998575
2783915640 found at iteration:998576
2783915064 found at iteration:998577
2783915046 found at iteration:998578
2783915406 found at iteration:998579
2783915460 found at iteration:998580
....

我试图通过打印每个调用的参数来理解回溯调用的逻辑，下面是一个摘录：

permute(0123746589, 7, 9)
permute(0123746589, 8, 9)
permute(0123746589, 9, 9)
permute(0123746598, 9, 9)
permute(0123746859, 8, 9)
permute(0123746859, 9, 9)
permute(0123746895, 9, 9)
permute(0123746985, 8, 9)
permute(0123746985, 9, 9)
permute(0123746958, 9, 9)

我只是不明白为什么输出没有按字典顺序产生？任何人，也许可以解释和建议如何纠正它，我的意思是，我有解决办法，但我真的希望能够使我的程序按预期的工作。

我听说递归回溯程序员通常只说：“它不工作，但我不知道为什么”或“它工作，但我不知道为什么”.

Answer 1

好的，明白了，必须重构整个过程，我采用了一种更简单的方法，过了一会儿，我自己也很难理解这个机制，这一直是编码不好的症状。无论如何，谢谢，这是词典输出的代码：

//Lexicographic Permutations, Project Euler Problem 24
#include <stdio.h>
#define TARGET 1000000 

int iteration=0;

int permute(char*,int);
int swap(int,int);
int indent(int);

char digits[10]="0123456789";
int available[10]={1,1,1,1,1,1,1,1,1,1};

int main(){
    char selected[10]={0};
    permute(selected,0);
}

int permute(char selectedSoFar[],int position){
//  indent(position);
//  printf("permute(%s, %d)\n",selectedSoFar,position);

    if (position==10){
        iteration++;
        if(iteration==TARGET) printf ("iteration %3d: %s\n",iteration, selectedSoFar);

    }else{
        for (int i=0 ; i<10 ; i++){
            if (available[i]==1){
                available[i]=0;
                selectedSoFar[position]=i+'0';
                permute(selectedSoFar,position+1);
                selectedSoFar[position]='\0';
                available[i]=1;
            }
        }
    }   
    return 0;
}

int indent(int level){
    while (level>0){
        printf("  ");
        level--;
    }
    return 0;
}

下面是它背后的机械原理(试图让它更清晰)。

permute(, 0)
  permute(0, 1)
    permute(01, 2)
      permute(012, 3)
        permute(0123, 4)
          permute(01234, 5)
            permute(012345, 6)
              permute(0123456, 7)
                permute(01234567, 8)
                  permute(012345678, 9)
                    permute(0123456789, 10)
iteration   1: 0123456789
                  permute(012345679, 9)
                    permute(0123456798, 10)
iteration   2: 0123456798
                permute(01234568, 8)
                  permute(012345687, 9)
                    permute(0123456879, 10)
iteration   3: 0123456879
                  permute(012345689, 9)