Перенос с повторяющимися буквами и последовательными буквами не одинаковый

Question

Я пытался решить вопрос о перестановке и не был действительно успешным. Я хочу сгенерировать все перестановки заданной длины, которые начинаются с буквы и заканчиваются тем же, и никакие две последовательные буквы не должны совпадать. Сгенерированные перестановки могут иметь повторяющиеся буквы.
Например,
, если массив имеет {a, b, c, d}, и мне нужны все перестановки, которые начинаются и заканчиваются на.
Ответ должен быть:
ABCA
Abda
АКБА
ACDA
Если массив {а, б, в, д, е}
Выход:
abcda
ABADA
abdca
абака
acbda
acada
acdba
Акаба
adbca
adaca
adcba
Adaba
abcba
Абеба
abdba
acbca
acaca
acdca
adbda
adcda
Adada

я даже хотел бы знать, есть ли какой-то способ, с помощью которого я могу непосредственно познакомиться с No.of решения я получить для массива по некоторой формуле ..
Спасибо всем заранее ..

Answer 1

Algoritm выглядит следующим образом. Вы начинаете с буквы a, а затем получаете набор всех букв, которые вы можете использовать следующим образом. Затем для каждого элемента из набора вы разворачиваете a до ab ac ad. Затем вы добавляете обратно для установки и удаления b, c, d из набора для каждого из новых слов соответственно. После этого вы делаете то же самое (рекурсия). Единственная сложная часть - это когда вы заканчиваете. Затем вам также нужно удалить письмо, с которого вы начали, прежде чем выбрать вторую для последней буквы.

Что касается математики формулы:

Обозначим T(n,l) как число «перестановок» длин l и алфавита размера n. Теперь мы можем разработать следующую рекурсию:

T(n,3) = n - 1 // a(something other than a)a 
T(n,k) = (n-1)^(l-2) - T(n, k-1) 

Что происходит в рекурсивном случае. Мы исходим из рассмотрения случая, когда последняя и вторая к последней букве могут быть равны.Итак, у нас есть a(letter other than previous, so (n-1) choices)^(l-2) и, наконец, мы выберем эти случаи, когда первая буква равна секунде последней, которая равна T(n, k-1).

Чтобы эффективно вычислить его на компьютере, используйте динамическое программирование или оповещение.

Answer 2

Вы можете использовать алгоритм next_permutation из STL

#include <iostream>  // std::cout 
#include <algorithm> // std::next_permutation, std::sort 

int main() { 
char mychars[] = "abc";; 

std::sort (mychars,mychars+3); 

std::cout << "The 3! possible permutations with 3 elements:\n"; 
do { 
    std::cout << mychars[0] << ' ' << mychars[1] << ' ' << mychars[2] << '\n'; 
} while (std::next_permutation(mychars,mychars+3)); 

std::cout << "After loop: " << mychars[0] << ' ' << mychars[1] << ' ' << mychars[2] << '\n'; 

return 0; 

ссылка - http://www.cplusplus.com/reference/algorithm/next_permutation/сильный текст

Answer 3

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

Math Ответ:

Если я правильно понимаю, что вы хотите, чтобы ваша строка, чтобы начать и начать с определенной буквы, «а», например. Тогда число перестановок зависит от размера вашего сгенерированного массива. Для описанной вами проблемы вам нужно понять свою строку как «a * a», где «» может принимать несколько значений. Звезда может быть заполнена 26 способами (количество букв в алфавите) минус количество букв, которые несовместимы с вашими правилами. Поэтому первая звезда имеет максимум 25 возможностей (потому что вы не можете повторить «a» в двух последовательных символах). у второй звезды может быть только 24 возможности из-за того, что она не может быть «а» или буквой перед ней (26-2 = 24). Затем, когда мы составляем возможности, у вас есть комбинация 25 * 24.

С строкой размера n символов (исключая первое и последнее, которые заданы с начала) у вас есть 25^(n-1) * 24 комбинаций.

Для алгоритма части:

См backtracking для легко реализовать, и достаточно быстрый способ генерировать то, что вам нужно. Вы просто просматриваете свою строку и устанавливаете эти неизвестные символы (* s) на значения, которые не повторяют одну и ту же букву, и так далее, пока вы не сгенерировали все значения.

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