Permutations

+10

Дан список nums различных целых чисел. Верните все перестановки этих значений — каждая должна быть списком, в котором каждое значение встречается ровно один раз, поэтому для n значений получится n! перестановок. Перечислите их в лексикографическом порядке: сравнивайте две перестановки по позициям, и порядок определяет первое различие. Для [1, 2, 3] это означает, что первой будет [1, 2, 3], а последней — [3, 2, 1].

Функция

permute(nums: integer-array) → integer-2d-array

numsinteger-array: значения, все разные, в любом порядке
Возвращаетinteger-2d-array: каждое упорядочение значений, перечисленное в лексикографическом порядке

Ограничения

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Все значения в nums различны.
nums могут располагаться в любом порядке.

Примеры

Ввод: nums = [3, 1, 2]
Вывод: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Пояснение: У трёх значений есть 3! = 6 вариантов упорядочивания. В отсортированном виде значения равны 1, 2, 3, поэтому сначала идут варианты, начинающиеся с 1, а [1, 2, 3] идёт перед [1, 3, 2], потому что 2 меньше 3 на второй позиции. Порядок входных данных не имеет значения.

Ввод: nums = [2, -1]
Вывод: [[-1, 2], [2, -1]]
Пояснение: Два значения можно записать в двух порядках. [-1, 2] идёт первым, потому что -1 меньше 2.

+13 скрытых тестов при отправке

Дополнительный вопрос

Имея одну последовательность, можешь ли ты получить следующую в лексикографическом порядке на месте за время O(n) и с использованием O(1) дополнительной памяти?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Список из n различных значений имеет n! упорядочиваний — 720 для шести значений, и в ответе нужно перечислить их все, поэтому объём работы составляет как минимум n × n!. Задача состоит в том, чтобы построить каждое упорядочивание ровно один раз и вывести их в лексикографическом порядке. Поиск с возвратом по отсортированным значениям, при котором каждый раз сначала выбирается наименьшее неиспользованное значение, позволяет сделать и то и другое одновременно.

Вставьте в каждый пропуск, затем отсортируйте

Идея

Стройте перестановки, добавляя по одному значению за раз. Если значений нет, есть одна перестановка — пустой список. Чтобы добавить значение 3 в перестановку [1, 2], поместите его в каждый из трёх промежутков: [3, 1, 2], [1, 3, 2] и [1, 2, 3]. Проделайте это для каждой имеющейся перестановки, и перестановки из k значений превратятся в перестановки из k+1 значений.

Каждая перестановка из k+1 значений строится ровно один раз: удалите из неё последнее добавленное значение — и получите единственную перестановку, из которой она выросла, а позиция последнего добавленного значения указывает промежуток. Поэтому количество перестановок растёт как 1, 2, 6, 24, а для n значений получается n! перестановок.

Они получаются не в нужном порядке. Для [1, 2, 3] первой строится перестановка [3, 2, 1], поэтому в конце нужно отсортировать их, сравнивая значения позиция за позицией. Эта сортировка — самая затратная часть: для сортировки n! перестановок потребуется примерно n! × log(n!) сравнений, и при каждом считывается до n значений. Для шести значений это примерно 720 × 9.5 × 6, то есть около 41,000 считываний. Кроме того, пока метод строит следующее поколение перестановок, он хранит в памяти целиком предыдущее.

Алгоритм

Начните со списка, содержащего одну пустую перестановку.
Для каждого значения в nums создайте новый список: для каждой уже имеющейся перестановки и каждого промежутка от 0 до её длины скопируйте перестановку, вставив значение в этот промежуток.
Замените старый список новым.
Отсортируйте перестановки по позициям и верните их.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Возврат с массивом used

Идея

Заполняйте n слотов слева направо. Для первого слота есть n кандидатов, для второго — n-1 и так далее; отсюда и берётся n!. Изобразите эти варианты в виде дерева: корень — это пустой путь, каждое ребро добавляет ещё одно значение, а каждый лист на глубине n — это готовый порядок. Для отсортированных значений 1, 2, 3 у корня есть дочерние узлы [1], [2] и [3]; у [1] есть дочерние узлы [1, 2] и [1, 3]; у каждого из них есть по одному листу.

Алгоритм с возвратом проходит это дерево, используя один общий path и флаг used для каждого значения. В каждом узле он перебирает значения и пропускает уже использованные. Для каждого свободного значения он выбирает его (помечает как использованное и добавляет в путь), исследует (рекурсивно переходит на уровень глубже), а затем отменяет выбор (удаляет его и помечает как свободное). Шаг отмены выбора восстанавливает состояние, которое было до цикла, поэтому следующее значение проверяется из того же узла. Путь длины n — это лист: сохраните его копию и вернитесь.

Порядок получается автоматически. Цикл сначала проверяет наименьшее свободное значение, а обход завершает все порядки с заданным префиксом, прежде чем перейти к другому префиксу. Поэтому все порядки, начинающиеся с 1, идут раньше любых порядков, начинающихся с 2, а среди них [1, 2, ...] идёт раньше [1, 3, ...]. Это лексикографический порядок. Именно поэтому сначала нужно отсортировать nums: цикл идёт по индексам, значит, индексы должны соответствовать порядку значений.

В дереве примерно e × n! узлов (e ≈ 2.72), и в каждом выполняется цикл длины n, поэтому время работы — O(n × n!), то есть того же порядка, что и размер ответа. Помимо результата, путь, флаги и стек вызовов содержат не более n элементов каждый.

Алгоритм

Отсортируйте значения и создайте массив used из n флагов со значением false.
Напишите explore(). Если в path содержится n значений, добавьте в результат его копию и выполните возврат.
В противном случае для каждого индекса i от 0 до n-1, значение которого свободно: отметьте его как использованное и добавьте values[i] (выбор), вызовите explore() (исследование), затем удалите его и отметьте как свободное (отмена выбора).
Один раз вызовите explore() и верните результат.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Ловушки и крайние случаи

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

Запись path вместо его копии. Все n! элементов в итоге оказываются одним и тем же списком, который становится пустым после завершения обхода.
Отмена выбора только наполовину. Если удалить значение, но оставить used[i] установленным, это значение больше не появится в последующих ветвях, и вы вернёте меньше n! перестановок.
Не сортировать nums перед началом. Обход всё равно найдёт все перестановки, но они будут следовать порядку входных данных, поэтому [3, 1, 2] будет указано первым.
Использование метода перестановки элементов (поменять местами nums[start] и каждую последующую позицию, выполнить рекурсивный вызов, поменять обратно) без итоговой сортировки. Он находит все n! перестановок, но для [1, 2, 3] выводит [3, 2, 1] перед [3, 1, 2].
Проверка, использовалось ли значение, с помощью поиска в path. Здесь это работает только потому, что значения различаются, и на каждом шаге требует n операций. Флаг для каждого индекса работает за O(1) и подходит даже при повторяющихся значениях.

Частые вопросы4

Сколько перестановок имеет список из n различных элементов?

n!, читается «n факториал»: n вариантов для первой позиции, n-1 для второй, и так далее до одного варианта для последней; всё это перемножается. Для трёх значений получается 6 порядков, для шести — 720, а для десяти уже 3,628,800, поэтому в задачах на перестановки n обычно небольшое.

Какова временная сложность генерации всех перестановок?

O(n × n!). Существует n! порядков, и на запись каждого требуется n шагов, поэтому ни один метод не может работать быстрее, если ему нужно вернуть их все. Поиск с возвратом достигает этой границы, а помимо вывода ему требуется O(n) памяти для текущего пути, флагов использования и рекурсии.

Почему перебор с возвратом генерирует перестановки в лексикографическом порядке?

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

Как сгенерировать перестановки, если во входных данных есть дубликаты?

Отсортируйте значения и на каждой позиции пропускайте значение, равное предыдущему, если эта предыдущая копия не используется: i > 0, values[i] == values[i-1] и !used[i-1]. Это заставляет размещать одинаковые значения в исходном порядке, поэтому каждый уникальный порядок строится один раз.

Python

def permute(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [3, 1, 2]

Ожидается

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]