Let’s say that you wanted to write some C++ to generate all permutations for char A[4] = {'A', 'B', 'C', 'D'};. How do you go about that?
the easiest way turns out is to leverage <algorithm>:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N=4; /* number of letters */
char A[N-1] = {'A', 'B', 'C', 'D'};
sort(A, A + N); /* requirement: this needs to be sorted */
do {
for (int i = 0; i < N; ++i) cout << A[i] << " "; cout << endl;
} while (std::next_permutation(A, A + 4));
return 0;
}
I would have preferred some recursive approach and not using <algorithm>:
#include <iostream>
#include <vector>
using namespace std;
// Find all the permutations of the 4 letters below.
char A[4] = {'A','B','C','D'};
bool used[4]; // tag letters from above when used so there's no reuse
vector<char> perm;
void permute() {
if (perm.size() == 4) {
for(auto x : perm) { cout << x; } cout << endl; /* print it */
return;
}
for (int i=0; i<4; i++) {
if(used[i]) continue; /* permutation: no reuse */
perm.push_back(A[i]); /* add current character */
used[i] = true; /* mark it as used */
permute(); /* >>> go again <<< */
perm.pop_back(); /* free the character */
used[i] = false; /* mark it unused */
}
}
int main() {
permute();
}
Turns out there exist a non-recursive algorithm discovered/invented/proposed by B. R. Heap in 1963. Great LaTeX rendering of the algorithm on Baeldung:
