A permutation of length n is an ordered collection without repetitions of the numbers 1, 2, ..., n. For example, [3, 1, 2] and [5, 4, 3, 2, 1] are permutations, but [1, 2, 1, 3] and [1, 2, 4] are not.
If the task is reduced to the fact that it is necessary to iterate over all permutations of length n, then you can use a convenient mechanism in C ++, which is called "next_permutation".
You can read more about it in documentation, but the point is that this function changes the passed array to subsequent permutation in lexicographic order (which is generally clear and its name).
To use next_permutation, you need to include the algorithm library (i.e. write #include <algorithm> at the beginning of the program)
Examples:
vector arr;
arr = { 1, 2, 3 }; // array is [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // pass the entire array to the function
// array is now [1, 3, 2]
arr = { 2, 3, 1 }; // array is [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // pass the entire array to the function
// array is now [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // it is possible to apply a function to a part of an array, but in practice this is rarely needed
// array is now [3, 2, 1]
In this case, the function has a boolean return value that is true if the next permutation was generated and false if there was no next one (the case when the maximum permutation in lexicographic order is passed to the function).
This makes it possible to use the function in a loop, which will allow us to iterate over all permutations at once. Due to 0-indexing, in practice it is often more convenient to work with a permutation of numbers from 0 to n - 1, although a permutation formally contains numbers from 1 to n. But fortunately, this does not lead to additional overlays in the code, because the next_permutation function is adapted to 0-indexed permutations (and even duplicate elements in an array, but you can find out more on your own).
In general, the code for iterating over all permutations looks like this:
intn; // permutation size
vectorperm(n); // perm is short for "permutation", i.e. "permutation"
for (int i = 0; i < n; i++)
perm[i] = i; // initialize initial permutation 0, 1, ..., n - 1
do {
// inside the loop we process the current permutation
} while (next_permutation(perm.begin(), perm.end())); // if there is no next permutation, then end the loop
This code runs in O(n! * f(n)), where f(n) is the time it takes you to process one particular permutation.
|