Перестановки с некоторыми фиксированными числами

Сгенерируйте все перестановки 2 4 5 и вставьте 3 и 1 в свою процедуру вывода. Просто запомните позиции, в которых они должны быть:

int perm[3] = {2, 4, 5};
const int N = sizeof(perm) / sizeof(int);

std::map<int,int> fixed;  // note: zero-indexed
fixed[1] = 3;
fixed[3] = 1;

do {
    for (int i=0, j=0; i<5; i++)
        if (fixed.find(i) != fixed.end())
            std::cout << " " << fixed[i];
        else
            std::cout << " " << perm[j++];
    std::cout << std::endl;
} while (std::next_permutation(perm, perm + N));

выходы

 2 3 4 1 5
 2 3 5 1 4
 4 3 2 1 5
 4 3 5 1 2
 5 3 2 1 4
 5 3 4 1 2

Я прочитал другие ответы, и я считаю, что они лучше, чем мои, для вашей конкретной проблемы. Однако я отвечаю на тот случай, если кому-то понадобится обобщенное решение вашей проблемы.

Недавно мне нужно было сгенерировать все перестановки трех отдельных непрерывных диапазонов [first1, last1) + [first2, last2) + [first3, last3). Это соответствует вашему случаю, когда все три диапазона имеют длину 1 и разделены только 1 элементом. В моем случае единственным ограничением является расстояние (first3, last3)> = distance (first1, last1) + distance (first2, last2) (которое, я уверен, можно было бы смягчить за счет дополнительных вычислительных затрат).

Мое приложение должно было генерировать каждую уникальную перестановку, но не ее обратную. Код здесь:

http://howardhinnant.github.io/combinations.html

И конкретная применимая функция - comb_discontinuous3 (которая создает комбинации) и ее использование в reversible_permutation :: operator (), который создает перестановки.

Это не готовое комплексное решение вашей проблемы. Но это набор инструментов, который можно использовать для решения обобщенной проблемы. Опять же, для вашей конкретной простой проблемы я рекомендую более простые решения, уже предложенные другими.

Помните, в каких местах вы хотите получить фиксированные номера. Удалите их из массива. Сгенерируйте перестановки как обычно. После каждой перестановки вставляйте фиксированные числа в те места, где они должны появиться, и выведите их.

Если у вас есть набор цифр {4,3,2,1,5} и вы знаете, что 3 и 1 не будут переставлены, то вы можете взять их из набора и просто сгенерировать набор мощности для {4, 2, 5}. Все, что вам нужно сделать после этого, - просто вставить 1 и 3 в их соответствующие позиции для каждого набора в наборе мощности.

Я опубликовал аналогичный вопрос, и там вы можете увидеть код для Powerset.