The problem is generally posed as given a string, print all permutations of it. For eg, the permutations of string ABC are ABC, ACB, BAC, BCA, CAB, CBA.
The standard solution is a recursive one, given below.
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}
This, runs into O(n*n!). Is this the best we can do or is there someway to make this faster?
You can use std::next_permutation. Please, notice it works correctly only on sorted array.
Good points about this solution: 1) It is standard 2) It is non-recursive
Here is an example (http://www.cplusplus.com/reference/algorithm/next_permutation/):
// next_permutation example
#include <iostream> // std::cout
#include <algorithm> // std::next_permutation, std::sort
int main () {
int myints[] = {1, 2, 3};
std::sort (myints, myints + 3);
std::cout << "The 3! possible permutations with 3 elements:\n";
do {
std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while (std::next_permutation (myints, myints + 3));
std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
return 0;
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments