1. Permutation and combination algorithms can be easily solved using recursive definitions. Here is sample code (not tested)
void RecursivePermute(string fixed, string remained) { if( remained == "" ) { cout << fixed << endl; } else { // break at every element and fix it for( size_t i = 0; i < remained.size(); i++ ) { string newFixed = fixed + remained[i]; string newRemained = remained.substr(0, i) + remained.substr(i+1);
RecursivePermute(newFixed, newRemained); } } }
Initial call
RecursivePermute(string(""), string("6174"));
2. Using state space tree. It is more space efficient and challenging to code (interesting too). The tree will have N! leaves and every path from root to leaf forms one permutation.
3. Generating permutations in order. We can make use of NextHigherPermutation() function and generate till we have no more moves in the set. It is easy to code the function. From right, find first element which is not in the order. Exchange the element with ceil value in the right part of array.
4. Johnson-Trotter algorithm. Based on move element it is interesting to code.
5. Generating subsets. We can use programs such as "snoob" to generate subsets. Each bit corresponds to presence/absence of element. Ofcourse it can only be used for combination generation.
6. Not sure, but I guess we can also use ranking/unranking algorithms for permutation generation.
I have atleast five approaches.
ReplyDelete1. Permutation and combination algorithms can be easily solved using recursive definitions. Here is sample code (not tested)
void RecursivePermute(string fixed, string remained) {
if( remained == "" ) {
cout << fixed << endl;
} else {
// break at every element and fix it
for( size_t i = 0; i < remained.size(); i++ ) {
string newFixed = fixed + remained[i];
string newRemained = remained.substr(0, i) + remained.substr(i+1);
RecursivePermute(newFixed, newRemained);
}
}
}
Initial call
RecursivePermute(string(""), string("6174"));
2. Using state space tree. It is more space efficient and challenging to code (interesting too). The tree will have N! leaves and every path from root to leaf forms one permutation.
3. Generating permutations in order. We can make use of NextHigherPermutation() function and generate till we have no more moves in the set. It is easy to code the function. From right, find first element which is not in the order. Exchange the element with ceil value in the right part of array.
4. Johnson-Trotter algorithm. Based on move element it is interesting to code.
5. Generating subsets. We can use programs such as "snoob" to generate subsets. Each bit corresponds to presence/absence of element. Ofcourse it can only be used for combination generation.
6. Not sure, but I guess we can also use ranking/unranking algorithms for permutation generation.