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

Question

Как эффективно генерировать перестановки числа (или символов в слове), если мне нужно определенное число / цифра в указанном месте?

Например, генерировать все числа с цифрой 3 в секундуместо с начала и цифра 1 на втором месте с конца числа.Каждая цифра в номере должна быть уникальной, и вы можете выбирать только из цифр 1-5 .

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

Я знаю, что есть функция next_permutation, поэтому я могу подготовить массив с числами {4, 2, 5} и отправьте это в цикле к этой функции, но как обрабатывать фиксированные позиции?

Answer 1

Сгенерируйте все перестановки 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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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