Как найти количество способов перестановки строки, удовлетворяющей приведенным ниже условиям?

Question

Мне дана строка, скажем, "abcd". Теперь я должен найти все строки, которые могут быть сгенерированы перестановкой его характера, такие

что-

1. Есть ровно четыре несоответствия в сгенерированных строках и,
2. невязок существует в паре, например, для -

строка - "ABCD" имеет три таких permutations- "BADC" , "cdab", "dcba".

Explanation-

Рассмотрим "абвг" и "BADC". В настоящее время существует ровно четыре несоответствие с, i.e- (а, б), (Ь, а), (в, г), (д, с) и эти несоответствия существует в паре.

Обратите внимание, что "ABCDE" имеет пятнадцать таких permutations- acbed, adebc, aedcb, baced, badce, baedc, cbaed, cdabe, ceadb, dbeac, dcbae, decab, ebdca, ecbda, edcba

Где я терплю неудачу? -

Я просто нахожу строки вручную, но это становится очень трудоемким для струн большой длины. Следовательно, мне нужно эффективное решение.

Answer 1

Если у вас есть строка длины n, состоящая из n разных букв, то номер, который вы найдете, это: n * (n - 1) * (n - 2) * (n - 3)/8.

Причина: Есть C(n, 4) способов выбрать 4 несоответствие мест от n писем, и для каждой такой четверки существует три способа их сопряжения.

Следовательно, результат C(n, 4) * 3 = n * (n - 1) * (n - 2) * (n - 3)/8.

---

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

---

Редактировать: Теперь предположим, что буквы могут повторяться. Ситуация сложнее. Я просто дам эскизы здесь.

Скажем, строка содержит m разных букв, встречающихся a_1, ..., a_m раз, соответственно. Также напишите b_i на номер C(a_i, 2).

Есть три случая:

• Случай 1: четыре несовпадений образуют два одинаковых пары, например, два a и два b перераспределены.

В этом случае у нас есть sum{b_i * b_j : 1 <= i < j <= m} разные строки. Это равно (sum{b_i}^2 - sum{b_i ^2})/2, выражение, которое может быть оценено в O(m) времени.

• Случай 2: четыре несоответствия содержат три разных буквы, например. один в паре с одним б, а другой в паре с одним с.

В этом случае сначала выберите букву, которая является общей для двух пар, допустим, это i-я буква; то нужно выбрать две другие буквы.

Напиши s на сумму a_i и t на сумму b_i. Если мы выберем две произвольные буквы из оставшихся s - a_i букв, мы должны исключить случаи, когда две буквы идентичны, что имеет t - b_i возможностей. Таким образом, есть C(s - a_i, 2) - (t - b_i) различные способы выбора двух других букв, поэтому b_i * (C(s - a_i, 2) - (t - b_i)) разные строки. Суммирование их для всех i дает общее количество различных строк в этом случае. Он все еще может быть оценен в O(m) времени.

• Дело 3: четыре разных буквы, например. один и один б образуют пару, и один с и один д форма другая пара.

Идея такая же. Во-первых, рассмотрим возможность выбора произвольных букв s. Затем мы должны исключить несколько случаев:

i. Все четыре буквы идентичны, у этого есть sum{C(a_i, 4)} чехлы;

ii.Три буквы идентичны, четвертый - другой, у этого есть sum{C(a_i, 3) * (s - a_i)} случаях;

iii. Две буквы идентичны, две другие одинаковы, это точно число, рассчитанное в случае 1;

iv. Две буквы идентичны, другие две разные, это точно число, рассчитанное в случае 2.

Итак, общее количество возможностей выбора четырех разных букв из всех писем s: C(s, 4) - [i] - [ii] - [iii] - [iv]. Как и раньше, это число должно быть умножено на 3, чтобы получить количество различных строк, поскольку каждая четверка дает 3 разные строки.

В целом, временная сложность O(m), что, очевидно, оптимально.