Перестановки и сочетания

Перестановки и сочетания

import math

# Permutations
n = 4
print(f'Permutations of {n} items: {math.factorial(n)}')
# 4! = 24

# Combinations
for k in range(n+1):
    print(f'C({n},{k}) = {math.comb(n,k)}')
# C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1
# Sum = 2^4 = 16 (total subsets)

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

def permutations(nums):
    result = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            result.append(list(path))
            return
        for i, num in enumerate(nums):
            if not used[i]:
                used[i] = True         # CHOOSE
                path.append(num)
                backtrack(path)        # EXPLORE
                path.pop()             # UNCHOOSE
                used[i] = False
    backtrack([])
    return result

print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Перестановки на основе обмена

def permutations_swap(nums):
    result = []
    def backtrack(start):
        if start == len(nums):
            result.append(list(nums))
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # CHOOSE (swap)
            backtrack(start + 1)                          # EXPLORE
            nums[start], nums[i] = nums[i], nums[start]  # UNCHOOSE (swap back)
    backtrack(0)
    return result

print(permutations_swap([1, 2, 3]))
# Same 6 permutations, different order

Перестановки II: обработка дубликатов

def permutations_unique(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            result.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]: continue
            # Skip if this num is a duplicate and the previous dup was not used
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return result

print(permutations_unique([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]] — 3, not 6

Следующая перестановка (лексикографический порядок)

def next_permutation(nums):
    n = len(nums)
    # Step 1: find rightmost i where nums[i] < nums[i+1]
    i = n - 2
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1
    if i >= 0:
        # Step 2: find rightmost j where nums[j] > nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Step 3: swap
        nums[i], nums[j] = nums[j], nums[i]
    # Step 4: reverse suffix after i
    nums[i+1:] = nums[i+1:][::-1]
    return nums

print(next_permutation([1, 2, 3]))  # [1,3,2]
print(next_permutation([3, 2, 1]))  # [1,2,3] (wraps)
print(next_permutation([1, 1, 5]))  # [1,5,1]

Поиск с возвратом для сочетаний размера k

def combinations(nums, k):
    result = []
    def backtrack(start, path):
        if len(path) == k:
            result.append(list(path))
            return
        for i in range(start, len(nums)):
            # Pruning: not enough elements left
            if len(nums) - i < k - len(path):
                break
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

print(combinations([1,2,3,4,5], 3))
# 10 combinations: C(5,3)
import math
print(math.comb(5,3))  # 10

Сумма сочетаний: неограниченное повторное использование

def combination_sum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(list(path))
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining: break  # all remaining are too big
            path.append(c)
            backtrack(i, path, remaining - c)  # reuse allowed: pass i, not i+1
            path.pop()
    backtrack(0, [], target)
    return result

print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]

Сумма сочетаний II: без повторного использования, с дубликатами

def combination_sum_ii(candidates, target):
    candidates.sort()
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(list(path))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break
            # Skip duplicates at same level
            if i > start and candidates[i] == candidates[i-1]:
                continue
            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])  # no reuse: i+1
            path.pop()
    backtrack(0, [], target)
    return result

print(combination_sum_ii([10,1,2,7,6,1,5], 8))
# [[1,1,6],[1,2,5],[1,7],[2,6]]

Буквенные сочетания телефонного номера

def letter_combinations(digits):
    if not digits: return []
    phone = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    result = []
    def backtrack(index, path):
        if index == len(digits):
            result.append(''.join(path))
            return
        for letter in phone[digits[index]]:
            path.append(letter)
            backtrack(index + 1, path)
            path.pop()
    backtrack(0, [])
    return result

print(letter_combinations('23'))
# ['ad','ae','af','bd','be','bf','cd','ce','cf']

Сравнение перестановок и сочетаний

# Pattern summary:
# Permutations: for i in range(n); if not used[i]; no start advancement
# Combinations: for i in range(start, n); advance start → i+1
# Combo Sum (reuse): for i in range(start, n); advance start → i (same)

# Quick reference:
import math
n = 5
print(f'Perm({n})   = n! = {math.factorial(n)}')
print(f'Comb({n},2) = C(n,k) = {math.comb(n,2)}')
print(f'Comb({n},3) = {math.comb(n,3)}')
# Also: subsets = sum(C(n,k) for k=0..n) = 2^n
print(f'Subsets({n}) = 2^n = {2**n}')

Сложность и советы для собеседования

import math

# Complexity for n=10
n = 10
print(f'Permutations(10): {math.factorial(n):,} results')
print(f'Combinations(10,5): {math.comb(n,5):,} results')
print(f'Subsets(10): {2**n:,} results')

# For interview: state which pattern
# 'This is a combinations problem because order doesnt matter'
# 'I will use a start index to avoid revisiting elements'
# 'Pruning: when sum exceeds target, break (after sorting)'

Проверка знаний

Итоги урока