Найти все перестановки / комбинации длины k из заданной строки

Question

Об этом меня спросили в интервью. Учитывая строку, мне пришлось написать программу, чтобы найти все перестановки / комбинации длины k. Так что для string = "cra" и length = 2 Следующее необходимо вернуть в вектор: "Ча", "кр", "RC", "ра", "ас", "ар". Повторение не допускается.

Есть предложения, как это сделать?

Я придумал, как использовать повторение. В основном зациклен на всех персонажах и добавил его в последовательность. Когда длина соответствует заданной длине, она добавляется к окончательному вектору.

Answer 1

Я бы искал что-то рекурсивное, потому что мне нравится рекурсия. Подстроки размера k в "cra":

• "c", за которым следуют подстроки размера k-1 в "ra"
• «r», за которым следуют подстроки размера k-1, - «ca»
• "a", за которым следуют подстроки размера k-1 в "cr"

Итак, если я напишу E, наборы из n символов, а e_i - его элементы.

• Substring (E, k) = {""}, если k = 0 (да, мне также нравится инициализация повторения в 0)
• и Подстрока (E, k) = Объединение (Подстрока (e_i + Подстрока (E \ e_i, k-1))) если k> 0

Подобные вещи лучше помещаются на черной доске, чем в цифровом тексте. Давайте попробуем простой текст:

Подстроки множества E размера k являются объединением e_i каждого элемента E подстрок, первая буква которых e_i.

Я чист? Я не знаю, ясно ли я.

После этого можно оптимизировать метод, торгуя временем вычислений для использования памяти, если вы храните промежуточные результаты, чтобы вам не приходилось вычислять их несколько раз (не имеет значения для n = 3, но это может определенно иметь значение, когда п становится большим). Если ваше начальное слово abcdefgh и k = 5, вы будете хранить такие вещи, как подстрока ("cdefgh", 3), так что вам не нужно будет вычислять его как для слов, начинающихся с a, так и для слов, начинающихся с b. Вы сэкономите много времени на вычисления, но при большом n может потребоваться много памяти. Если у вас есть пороговое значение для памяти, лучше хранить подстроки для наименьшего k, как те, которые будут запрашиваться чаще всего (конец дерева рекурсии).

Последний вопрос: как его хранить? Я бы выбрал карту, используя пару ("cdefgh", 3) или даже только "cdefgh" в качестве ключа и набор подстрок в качестве значения.

Answer 2

Как упомянул Слава , вы могли бы использовать std::next_permutation, но у меня есть чувство, что интервьюер хотел увидеть вашу техническую способность понять, как работают химические завесы и сочинения.

Здесь - полезная ссылка. Он использует Java / C # , я посмотрел на него, и, похоже, его легко конвертировать в C ++.

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

Надеюсь, вы найдете это полезным для следующих интервью. :)