Permutacion, C++ (gcc)

Permutacion

#include <iostream>
#include <vector>
using namespace std;

// Choose n keys from dict to make a permutation, and we already know the first cur keys in permutation.
struct Problem {
	vector<int> dict;
	int n;
	
    vector<int> permutation;
	int cur;
};

bool is_solved(const Problem &p){
	if(p.cur==p.n) return true;
	return false;
}

void do_when_solved(const Problem &p){
	for(int i=0;i<p.permutation.size();i++) printf("%d ",p.permutation[i]);
	printf("\n");
}

bool can_be_used(const Problem &p, int key){
	bool not_in_current_permutation=true;
	for(int j=0;j<p.cur;j++){
		if(key==p.permutation[j]){
			not_in_current_permutation=false;
			break;
		}
	}
	return not_in_current_permutation;
}

vector<Problem> make_subproblems(const Problem &p){
	vector<Problem> subproblems;
	for(int i=0;i<p.dict.size();i++){
		if(can_be_used(p, p.dict[i])){
			Problem subproblem=p;
			subproblem.permutation[p.cur]=p.dict[i];
			subproblem.cur++;
			subproblems.push_back(subproblem);
		}
	}
	return subproblems; 
}

void solve(const Problem &p){
	if(is_solved(p)){
		do_when_solved(p);
	}else{
		vector<Problem> subproblems=make_subproblems(p);
		for(int i=0;i<subproblems.size();i++){ 
			solve(subproblems[i]);
		}
	}
};

Problem permutation_of_1_to_(int n){
	Problem p;
    p.dict.resize(n);
    for(int i=0;i<n;i++) p.dict[i]=i+1; // the dict is [1,2,3,...,n]
	p.n=n; // we need choose n keys.
	p.cur=0; // we already know 0 keys of permutation
	p.permutation.resize(n); // prepare the space
	return p;
}

int main(){
	Problem the_problem=permutation_of_1_to_(5);
	solve(the_problem);
	return 0;
}


run \| edit \| history \| help	0