Is it possible to manipulate the current permutation sequence in order to skip (in my case) "useless" sequences?
If that isn't possible, would a custom implementation of a permutation iteration be as fast as std::next_permutation?
An example:
1 2 3 4 5 6 7 ...
1 3 2 4 5 6 7 ...
Detecting that "2" at the 2nd position isn't valid, leads to skipping every permutation which begins with "1, 2".
You would have to write some custom rules for that. A smart way to do this would be to write a code, in which whenever you have a set of permutations which are not valid, you jump to the next permutation you can get which will be valid.
For eg, in the above case, knowing that 2 at 2nd position is invalid, you could write the code to swap 2 and 3, and ensure that the permutation then achieved is the smallest one possible with 3 in that location, and so on.
Also, if you were writing your own implementation of next_permuation, ensure that the internal functioning is as close to that of next_permutation. You can read about it here: std::next_permutation Implementation Explanation
Yes, this is possible, and it's not hard once you understand how next_permutation works.
In short, there are N! permutations of N items. However, only one of them is sorted. 1 2 3 4 5 6 7 for instance is the first of 5040 permutations. Viewed as a string (lexicographically) the next permutation is the one that sorts directly after that: 1 2 3 4 5 7 6. It particular, the first 5 elements are unaltered. The next permutation alters the 5th element because the last 2 elements are in reverse order.
So, in your case, once you've found an illegal permutation, you'd have to explicitly calculate the next legal permutation by sort order. If 1 2 is the only illegal prefix then 1 3 2 4 5 6 7 is obviously the next valid permutation.
In general, look at your illegal pattern, determine which positions you have to increase because they violate constraints, and come up with the next valid values for those positions (if your pattern is small enough, you can brute-force this). Then fill in the remaining numbers in sorted order.
