Как заставить прыжки с std :: next_permutation

Question

Можно ли манипулировать текущей последовательностью перестановок, чтобы пропустить (в моем случае) «бесполезные» последовательности?

Если это невозможно, выполнялась ли обычная реализация итерации перестановки так же быстро, как std :: next_permutation?

Пример:

1 2 3 4 5 6 7 ...

1 3 2 4 5 6 7 ...

Обнаружение, что "2" на 2-м положении ISN» t valid, приводит к пропуску каждой перестановки, которая начинается с «1, 2».

Answer 1

Для этого вам придется написать некоторые пользовательские правила. Разумным способом сделать это было бы написать код, в котором всякий раз, когда у вас есть недопустимый набор перестановок, вы переходите к следующей перестановке, которую вы можете получить, которая будет действительной.

Например, в приведенном выше случае, зная, что 2 в 2-й позиции недействительны, вы можете записать код для замены 2 и 3 и убедиться, что достигнутая перестановка является наименьшей из возможных с 3 в этом месте, и так далее.

Кроме того, если вы пишете собственную реализацию next_permuation, убедитесь, что внутреннее функционирование так же близко, как и к функции next_permutation. Вы можете прочитать об этом здесь: std::next_permutation Implementation Explanation

Answer 2

Да, это возможно, и это не сложно, как только вы поймете, как работает next_permutation.

Одним словом, существует N! перестановки из N элементов. Однако только один из них сортируется. 1 2 3 4 5 6 7, например, является первой из 5040 перестановок. В качестве строки (лексикографически) следующая перестановка является следующей, которая сортируется непосредственно после этого: 1 2 3 4 5 7 6. В частности, первые 5 элементов не изменяются. Переменная next изменяет 5-й элемент, потому что последние 2 элемента находятся в обратном порядке.

Итак, в вашем случае, если вы обнаружили незаконную перестановку, вам нужно будет явно вычислить следующую законную перестановку по порядку сортировки. Если 1 2 является единственным незаконным префиксом, то 1 3 2 4 5 6 7, очевидно, является следующей допустимой перестановкой.

В целом, посмотрите на свой незаконный шаблон, определите, какие позиции у вас есть , увеличьте, потому что они нарушают ограничения и вызывают следующие допустимые значения для этих позиций (если ваш шаблон достаточно мал, это усилие). Затем заполните оставшиеся номера в отсортированном порядке.