Warum hört meine Backtracking-Funktion zum Erzeugen von Permutationen nie auf?

Question

Ich habe versucht, die folgende Funktion mit Backtracking zu schreiben, um alle Permutationen der ersten natürlichen Zahlen n zu generieren. Das Problem ist, dass es über jede Zahl auf jeder Ebene geht, bevor Sie sich für die letzte Zahl in meiner for-Schleife entscheiden, unabhängig von irgendwelchen Einschränkungen. Deutlicher ausgedrückt, Schleifen es unendlich folgende Ausgabe:

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 

Wenn ich die folgenden Einschränkungen zu entfernen:

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

das Programm aus:

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 

, die eindeutig nicht korrekt ist ...

Ich habe den folgenden Backtracking-Basisalgorithmus verwendet, der von meiner Universität zum Schreiben bereitgestellt wurde g meine Funktion:

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

Ich bin nicht sicher, wie ich das Problem beheben werde soll, aber ich vermute, dass es etwas mit meinem c Variable zu tun hat. Es soll anzeigen, ob die bereits ausgewählten Elemente jemals zu einer Lösung gehören können.

Ich möchte keine anderen Lösungen zur Lösung des Permutationsproblems, da ich Zugang zu einer Lösung habe. Ich möchte nur wissen, was mit meiner Argumentation/Codierung falsch ist, da ich diese Übung gemacht habe, um Backtracking zu verstehen.

#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, ich habe es gelöst. Das Hauptproblem war, dass ich eine für Schleife hatte, die mein nächstes Element innerhalb einer anderen do/while Schleife auswählte, die bereits die gleiche Sache tat. Deshalb hat die Funktion alle möglichen Werte durchlaufen.

ich losgeworden der für Schleife, eliminiert ich einige andere Entlassungen und hier ist der Arbeitscode des nicht-rekursive Rückzieher Permutationen 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; 
}