Question

Cine poate sa-mi explice algoritmul recursiv de generare a permutarilor ? Multumesc anticipat!

Answer 1

#include<iostream>
#include<cstdio>

using namespace std;

int a[10],b[10];
void back(int x, int y);

int main()
{
    int n;
    cout<<"introdu marimea vectorului"<<endl<<"n=";
    cin>>n;
    cout<<"generam permutari pentru valorile [1,"<<n<<"]"<<endl;
    back(1,n);
    return 0;
}
void back(int k,int lungime) //parametrii primiti sunt elementul curent din
                                            //vectorul a[i] si marimea vectorului a[i]
{
    int contor=1;
     if(k-1 == lungime) //daca valoarea elementului curent este
                                  //egala cu marimea vectorului a[i] => am
                                  //parcurs tot vectorul a[i]
     {
         for(int i = 1; i <= lungime;i++)
         {
            if(a[i]!=0) //nu afisam solutiile incomplete
            {
                if(contor%lungime==0) //daca numarul de elemente este egal 
                                                     //cu marimea vectorului
                {
                    cout<<a[i]<<endl; //sarim pe rand nou
                }
                else
                {
                    cout<<a[i]; // si afisam solutia
                }
            }
            contor++;
         }
     }
     else //daca nu s-a parcurs tot vectorul
     {
         for(int  i = 1; i <= lungime; i++)
         {
            if(!b[i])  //daca valoarea nu este folosita
            {
                a[k] = i;
                b[i] = 1; //o folosim
                back(k+1,lungime); // apoi trecem la pasul urmator
                b[i] = 0; // si o eliberam
            }
         }
     }
}