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

Question

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

например. Сгенерировать все числа с digit 3 на втором месте с начала и digit 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

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

Answer 3

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

Я разместил similar question и там вы можете увидеть код для электросети.

Answer 4

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

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

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

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

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

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