Генерация всех перестановок

Генерация всех перестановок (Permutations)

Это классическая задача на рекурсию и backtracking. Требует понимания комбинаторики и алгоритмов поиска.

1. Анализ проблемы

Перестановка — это переупорядочение элементов списка.

Количество перестановок: n! (факториал)

Для [1, 2, 3]: 3! = 6 перестановок
Для [1, 2, 3, 4]: 4! = 24 перестановки

Рекурсивная идея:

perms([1, 2, 3]) =
  [1] + perms([2, 3])
  [2] + perms([1, 3])
  [3] + perms([1, 2])

2. Решение 1: Встроенная функция (самое простое)

from itertools import permutations

def get_permutations_builtin(nums: list[int]) -> list[list[int]]:
    """Использование встроенной функции itertools."""
    return [list(perm) for perm in permutations(nums)]

# Тестирование
print(get_permutations_builtin([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Анализ:

• Время: O(n! × n) — n! перестановок, каждую копируем за O(n)
• Память: O(n! × n) — результат

3. Решение 2: Рекурсия с backtracking (правильно)

def get_permutations_recursive(nums: list[int]) -> list[list[int]]:
    """Генерация перестановок рекурсией."""
    result = []
    
    def backtrack(path, remaining):
        # Базовый случай: если нет оставшихся элементов
        if not remaining:
            result.append(path[:])
            return
        
        # Рекурсивный случай: пробуем каждый элемент
        for i in range(len(remaining)):
            # Выбираем элемент
            element = remaining[i]
            
            # Добавляем в текущую перестановку
            path.append(element)
            
            # Рекурсивно строим остаток
            new_remaining = remaining[:i] + remaining[i+1:]
            backtrack(path, new_remaining)
            
            # Backtrack: удаляем элемент
            path.pop()
    
    backtrack([], nums)
    return result

# Тестирование
print(get_permutations_recursive([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Визуализация дерева рекурсии для [1, 2, 3]:

                    []
        /           |          \
       1             2            3
      /    \        /   \        /   \
    [1]    [1]   [2]   [2]   [3]   [3]
    /  \   /  \   /  \  / \   / \  / \
   2    3 3    2 1    3 3   1 1    2 2   1
   |    |  |   |  |   |  |  |  |   |  |  |
[1,2] [1,3] [1,3] [1,2] [2,1] [2,3] [3,1] [3,2] [2,1] [2,3] [1,2] [1,3] [2,3] [3,2] [1,3] [3,1] [1,2] [2,1]

Результат: 6 перестановок

4. Решение 3: Swap-based (оптимальнее)

Место swap-based подхода: манипулируем индексами вместо создания новых массивов.

def get_permutations_swap(nums: list[int]) -> list[list[int]]:
    """Генерация перестановок через swapping."""
    result = []
    
    def backtrack(arr, left, right):
        # Базовый случай: весь массив переставлен
        if left == right:
            result.append(arr[:])
            return
        
        # Пробуем поменять каждый элемент
        for i in range(left, right + 1):
            # Swap
            arr[left], arr[i] = arr[i], arr[left]
            
            # Рекурсия
            backtrack(arr, left + 1, right)
            
            # Unswap (backtrack)
            arr[left], arr[i] = arr[i], arr[left]
    
    backtrack(nums[:], 0, len(nums) - 1)
    return result

print(get_permutations_swap([1, 2, 3]))

Почему лучше?

• Не создаём новые массивы remaining в каждом вызове
• Операции swap O(1) вместо slice O(n)
• Более эффективно по памяти

Анализ:

• Время: O(n! × n) — N! перестановок, копирование каждой O(n)
• Память: O(n! × n) для результата + O(n) для стека рекурсии

5. Решение 4: Итеративный подход (Лексикографический порядок)

def get_permutations_iterative(nums: list[int]) -> list[list[int]]:
    """Генерация перестановок итеративно."""
    result = [sorted(nums)]  # Начинаем с отсортированного
    
    while True:
        # 1. Найти наибольший индекс i такой, что nums[i] < nums[i+1]
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        # Если такого индекса нет, это последняя перестановка
        if i == -1:
            break
        
        # 2. Найти наибольший индекс j такой, что nums[i] < nums[j]
        j = len(nums) - 1
        while j > i and nums[j] <= nums[i]:
            j -= 1
        
        # 3. Поменять nums[i] и nums[j]
        nums[i], nums[j] = nums[j], nums[i]
        
        # 4. Развернуть nums[i+1:]
        nums[i + 1:] = reversed(nums[i + 1:])
        
        # Добавить в результат
        result.append(nums[:])
    
    return result

print(get_permutations_iterative([1, 2, 3]))

Как это работает? Лексикографический порядок:

[1, 2, 3]  ← начало (отсортировано)
[1, 3, 2]  ← найти 2 и 3, поменять, развернуть
[2, 1, 3]  ← найти 1 и 3, поменять, развернуть
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]  ← конец (обратный порядок)

6. Полная реализация с тестами

from typing import List
import unittest

class Solution:
    @staticmethod
    def permute(nums: List[int]) -> List[List[int]]:
        """Оптимальный способ: swap-based backtracking."""
        result = []
        
        def backtrack(arr, left):
            if left == len(arr) - 1:
                result.append(arr[:])
                return
            
            for i in range(left, len(arr)):
                arr[left], arr[i] = arr[i], arr[left]
                backtrack(arr, left + 1)
                arr[left], arr[i] = arr[i], arr[left]
        
        backtrack(nums, 0)
        return result


class TestPermutations(unittest.TestCase):
    
    def test_three_elements(self):
        """Пример из задачи."""
        nums = [1, 2, 3]
        result = Solution.permute(nums)
        expected = [
            [1, 2, 3], [1, 3, 2],
            [2, 1, 3], [2, 3, 1],
            [3, 1, 2], [3, 2, 1]
        ]
        self.assertEqual(len(result), len(expected))
        self.assertTrue(all(perm in expected for perm in result))
    
    def test_single_element(self):
        """Один элемент."""
        nums = [1]
        result = Solution.permute(nums)
        expected = [[1]]
        self.assertEqual(result, expected)
    
    def test_two_elements(self):
        """Два элемента."""
        nums = [1, 2]
        result = Solution.permute(nums)
        self.assertEqual(len(result), 2)
        self.assertIn([1, 2], result)
        self.assertIn([2, 1], result)
    
    def test_four_elements(self):
        """Четыре элемента (24 перестановки)."""
        nums = [1, 2, 3, 4]
        result = Solution.permute(nums)
        self.assertEqual(len(result), 24)
        # Проверяем, что все уникальны
        unique_perms = {tuple(perm) for perm in result}
        self.assertEqual(len(unique_perms), 24)
    
    def test_duplicates(self):
        """С дубликатами (если нужны уникальные)."""
        # Для дубликатов нужна отдельная задача
        # Здесь просто проверяем, что алгоритм работает
        nums = [1, 1, 2]
        result = Solution.permute(nums)
        # Будут дубликаты в результате
        self.assertEqual(len(result), 6)

if __name__ == '__main__':
    unittest.main()

7. Особый случай: уникальные перестановки (с дубликатами)

def permute_unique(nums: List[int]) -> List[List[int]]:
    """Генерация уникальных перестановок при наличии дубликатов."""
    result = []
    nums.sort()  # Отсортируем для правильного обхода дубликатов
    
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        
        seen = set()  # Отслеживаем уже использованные элементы
        for i in range(len(remaining)):
            if remaining[i] in seen:
                continue  # Пропускаем дубликаты
            
            seen.add(remaining[i])
            
            path.append(remaining[i])
            new_remaining = remaining[:i] + remaining[i+1:]
            backtrack(path, new_remaining)
            path.pop()
    
    backtrack([], nums)
    return result

print(permute_unique([1, 1, 2]))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

8. Сравнение методов

9. Анализ сложности

Количество рекурсивных вызовов:
Уровень 0 (выбор 1-го элемента): n вызовов
Уровень 1 (выбор 2-го элемента): n × (n-1) вызовов
Уровень 2 (выбор 3-го элемента): n × (n-1) × (n-2) вызовов
...
Итого: n! вызовов

Время:
- n! вызовов функции backtrack
- Каждый вызов O(1) операций (кроме копирования)
- Копирование результата: n! × O(n) = O(n! × n)

Мемория (стек):
- Глубина рекурсии: O(n)
- Размер каждого фрейма: O(n)
- Итого: O(n²)

10. Оптимизация для больших n

Для больших n перестановки неэффективны (n! растет экспоненциально):

n=5:  5! = 120
n=10: 10! = 3,628,800
n=12: 12! = 479,001,600  ← уже медленно!

Для таких случаев используйте:

• Комбинации вместо перестановок
• Ленивые генераторы (yield)
• Параллельные вычисления

11. Ленивая генерация (с yield)

def permutations_generator(nums: List[int]):
    """Генерирует перестановки по одной за раз."""
    
    def backtrack(path, remaining):
        if not remaining:
            yield path
            return
        
        for i in range(len(remaining)):
            new_path = path + [remaining[i]]
            new_remaining = remaining[:i] + remaining[i+1:]
            yield from backtrack(new_path, new_remaining)
    
    yield from backtrack([], nums)

# Использование
for perm in permutations_generator([1, 2, 3]):
    print(perm)

Вывод

Для генерации перестановок:

1. На интервью: Swap-based backtracking (правильно, эффективно)
2. В production: itertools.permutations (надёжно, оптимизировано)
3. Для лени: Generator с yield (экономит память)
4. С дубликатами: Отсортировать и пропускать повторы
5. Сложность: O(n!) — неизбежна, это количество результатов

Это часто задаваемая задача — покажите несколько подходов!