cod backtracking

[•dornescuvlad]

Cod:

void back(long int nivel)
{
    long int i;
     if (nivel==n+1)
        {
        for (i=1;i<=n;i++) printf("%ld ",st[i]);
        printf("\n");
        return;
        }
 
    for (i=1;i<=n;i++)
        if (!is[i])
        {
           st[nivel]=i;
            is[i]=1;            back(nivel+1);
           is[i]=0;     }}

imi explicati si mie acest cod de backtracking pentru permutari

[•peanutz]

Voi reface putin structura si voi adauga cate un comentariu la liniile relevante

Cod:

int is[NMAX+1], st[NMAX+1];
int n;

void back(long int nivel) //nivel este numarul de elemente -1 pe care il are permutarea deja si se incearca genererea elementului cu numarul de ordine nivel
{
    long int i;
    if (nivel==n+1) //daca am o permutare cu n elemente, o afisez si termin executia generarii curente
    {
        for (i=1;i<=n;i++) printf("%ld ",st[i]);
        printf("\n");
        return; //ies din functie 
    }
 
    for (i=1;i<=n;i++) 
        if (!is[i]) //incerc pe rand sa pun fiecare element in permutare daca el nu este deja prezent
        {
            st[nivel]=i; //pun elementul i pe pozitia nivel din permutare

            is[i]=1; //marchez elementul i ca si prezent in permutarea curenta de dimensiunea nivel
            back(nivel+1); //incerc sa generez urmatorul element din permutare
            is[i]=0; //cand ma intorc din recursivitate scot elementul i din multime    
        }
}

Apelezi functia in felul urmator: back(1).

Acum... Probabil ca nu ai inteles mare lucru daca nu ai mai lucrat backtracking/recursivitate. Trebuie sa intelegi cum functioneaza stiva sistemului. Cel mai ok ar fi sa faci debugging intr-un ide care are watch si sa urmaresti cum se modifica valoriile variabilelor in cursul executiei programului. Spor