Это вторая статья из серии о вопросах на собеседовании по программированию и о том, как их продумать и решить! Если вы хотите начать с начала, посмотрите даже вхождение!
В этой статье рассматривается очень распространенный вопрос на собеседовании, все варианты набора. ‘Реализуйте функцию, которая получает все перестановки или порядок заданной строки. Например, если вводится «abc», вывод должен быть [‘abc’, ‘acb’, ‘cab’, ‘cba’, ‘bca’, ‘bac’].
Анализ
Многие люди слышат слово перестановка и пугаются, поэтому давайте сначала разберемся, что такое перестановка на самом деле.
Перестановка относится к действию расположения всех членов множества в некую последовательность или порядок.
Легкий! Ну .. не совсем, но, по крайней мере, теперь мы знаем, что нам нужно вернуть в конце. То есть, если нам дано «abc»; результат должен быть:
[ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Давайте сначала посмотрим, как можно естественным образом решить эту проблему. Если бы задано «abc», я бы, естественно, отделил первую букву и нашел все перестановки следующих двух букв. Итак, для «abc» у меня было бы:
a bc a cb b ac b ca c ab c ba
В этом случае я сразу вспоминаю рекурсию, потому что мы не знаем, насколько большой будет строка в наших тестовых примерах. Итак, для всех букв в строке мы можем взять одну букву строки и добавить ее ко всем ее перестановкам без буквы в ней. В рекурсии нам нужен наш базовый случай, когда мы хотим остановить наш рекурсивный вызов. В этом случае, когда строка состоит из одного символа, мы вернем этот символ.
permutations(abc) = a + permutations(bc) +
b + permutations(ac) +
c + permutations(ab)
permutations(ab) = a + permutations(b) +
b + permutations(a)
permutations(a) = a
Псевдокод
function getAllPermutations (string)
define results
if string is a single character
add the character to results
return results
for each char in string
define innerPermutations as a char of string
set innerPermutations to getAllPermutations (without next char)
foreach string in innerPermutations
add defined char and innerPermutations char
return results
Сложность
Сложность описанного выше алгоритма по времени и пространству должна быть такой же, как и количество произведенных элементов. Количество уникальных перестановок любого набора размера n равно n!, Поэтому временная и пространственная сложность нашего алгоритма равна O (n!).
Код
Этот пост написал один из инструкторов Banyan Codecamp, нового учебного курса по программированию, разработанного с единственной целью: превратить начинающих программистов в способных инженеров под руководством старших инженеров. Получи высшее образование, сделай шестизначное число и учись на прекрасном острове Бали. Чтобы узнать больше, посетите www.codeinbali.com.
