permutari.cpp

permutari.cpp

#include <iostream>
#define FIN "permutari.in"
#define FOUT "permutari.out"
#define SIZE 100

using namespace std;
/*n = 3

n! = 1 2 3 = 6 permutari


valori:(1,2,3)nivel 3: 1
       (1,2,3)nivel 2: 3
       (1,2,3)nivel 1: 2

1 2 3       
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/


int stack[ SIZE ], 
    n, 
    level;

void init() {

	stack[ level ] = 0;	
}

int succ() {

	if(stack[level] < n) {

		stack[level]++;

		return 1;
	}

	return 0;
}


int valid() {

	for(int i = 1; i < level; ++i) {

		 if(stack[i] == stack[level]) return 0;
	}

	return 1;
}

int sol() {

	return level == n;
}


void display_solution() {

     for(int i = 1; i <= n; ++i) cout<<stack[i]<<" ";	


     cout<<endl;	

}

//varianta iterativa
void backtracking() {

      int h, v;

      level = 1;      

      init(); //stack[level] = stack[1] = 0

      while(level > 0) {

            h = 1;
            v = 0;

            while(h && !v) {
            	h = succ();
            	if(h) {
            		v = valid();
            	}
            }   

            if( h ) {

                 if(sol()) {
                 	display_solution();
                 }  else {
                 	level++;
                 	init();
                 }
            } else {
            	level--;
            }
      }
}


int main(int argc, char const *argv[])
{
                
        cout<<"n=";  
        cin>>n;

        backtracking();
    	return 0;
}