Permutacje i kombinacje
Wyliczać wszystkie permutacje listy — zarówno z powtarzającymi się elementami, jak i bez nich — oraz generować wszystkie k-kombinacje i warianty sumy kombinacji
Permutacje i kombinacje to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Permutacje a kombinacje
Permutacje to ułożenia, w których kolejność ma znaczenie: [1,2,3] i [3,2,1] są różne. Liczba permutacji n elementów wynosi n!. Kombinacje to wybory, w których kolejność nie ma znaczenia: wybór {1,2} jest taki sam jak {2,1}. Liczba k-kombinacji spośród n elementów wynosi C(n,k) = n! / (k! × (n-k)!). Oba wzorce są kluczowe w zadaniach rekrutacyjnych dotyczących zliczania, wyliczania i wybierania elementów.
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)Generowanie wszystkich permutacji
Należy użyć boolowskiej tablicy used do śledzenia elementów znajdujących się w bieżącej ścieżce. Na każdym etapie należy wypróbować każdy nieużywany element. Po zakończeniu przeszukiwania element należy ponownie oznaczyć jako nieużywany. W przeciwieństwie do podzbiorów permutacje nie korzystają z indeksu start, ponieważ elementy mogą być używane w dowolnej kolejności. Rekurencja kończy się, gdy len(path) == n.
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]]Permutacje oparte na zamianie elementów
Alternatywą jest zamiana elementu na pozycji start z każdym elementem od start do n-1, wywołanie rekurencji, a następnie cofnięcie zamiany. Tablica jest modyfikowana bezpośrednio, dzięki czemu nie potrzeba tablicy used. Kluczowa obserwacja jest taka, że na każdym poziomie wszystkie elementy na lewo od start są ustalone, a wybierany jest element, który zostanie umieszczony na pozycji start. To podejście jest nieco oszczędniejsze pod względem pamięci i stanowi podstawę algorytmu Heap's algorithm.
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 orderPermutacje II: obsługa duplikatów
Gdy dane wejściowe zawierają duplikaty (np. [1, 1, 2]), podejście z tablicą used generuje powtarzające się permutacje. Rozwiązanie polega na posortowaniu tablicy, a następnie pominięciu duplikatu, jeśli poprzedni identyczny element nie został użyty w tym wywołaniu rekurencyjnym. Warunek to: if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. Wymusza on wybieranie duplikatów od lewej do prawej.
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 6Następna permutacja (porządek leksykograficzny)
Next Permutation (LeetCode 31) przekształca tablicę w miejscu w jej następną, większą leksykograficznie permutację. Algorytm: (1) Znajdź najbardziej prawy indeks i, dla którego nums[i] < nums[i+1]. (2) Znajdź najbardziej prawy indeks j, dla którego nums[j] > nums[i]. (3) Zamień nums[i] i nums[j]. (4) Odwróć końcówkę za indeksem i. Jeśli taki indeks i nie istnieje, odwróć całą tablicę (następuje przejście do najmniejszej permutacji).
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]Backtracking dla k-kombinacji
Należy wygenerować wszystkie kombinacje k elementów spośród n (LeetCode 77). Należy użyć indeksu początkowego, podobnie jak w przypadku podzbiorów, aby uniknąć ponownego odwiedzania elementów i zachować posortowaną kolejność. Przycinanie następuje, gdy pozostaje mniej niż k - len(path) elementów: if len(nums) - i + 1 < k - len(path): break. Jest to odpowiednik wcześniejszej funkcji combine(n, k), ale działający na rzeczywistej tablicy.
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)) # 10Combination Sum: wielokrotne użycie elementów
Combination Sum (LeetCode 39) pozwala używać każdej liczby dowolną liczbę razy. Różnica w porównaniu ze standardowymi kombinacjami polega na tym, że zamiast przesuwać start do i+1, przekazuje się i (ten sam indeks), aby umożliwić ponowne użycie bieżącego elementu. Przycinanie: jeśli pozostały target osiągnie wartość 0, należy zapisać ścieżkę; jeśli stanie się ujemny, należy zakończyć przeszukiwanie. Sortowanie umożliwia wcześniejsze zakończenie, gdy wszyscy pozostali kandydaci przekraczają pozostały target.
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]]Combination Sum II: bez ponownego użycia, z duplikatami
Combination Sum II (LeetCode 40) używa każdej liczby najwyżej raz, ale dane wejściowe mogą zawierać duplikaty. Stosuje się tu połączenie dwóch technik: przesuwanie start do i+1 (bez ponownego użycia) oraz pomijanie duplikatów na tym samym poziomie (if i > start and nums[i] == nums[i-1]: continue) po posortowaniu tablicy. Jest to połączenie obsługi duplikatów z Subsets II oraz ograniczenia braku ponownego użycia z combinations.
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]]Kombinacje liter numeru telefonu
Letter Combinations (LeetCode 17) odwzorowuje każdą cyfrę na litery na klawiaturze telefonu i generuje wszystkie możliwe kombinacje liter dla danego ciągu cyfr. Jest to problem backtrackingu, w którym na każdej pozycji wybieramy jedną literę z odwzorowania cyfry i wywołujemy rekurencję. Dla ciągu długości n, przy średnio k literach przypadających na cyfrę, złożoność czasowa wynosi O(kⁿ).
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']Porównanie permutacji i kombinacji
Kluczowe różnice strukturalne: Permutacje — brak indeksu początkowego, należy użyć tablicy used lub zamian, aby uniknąć ponownego użycia, drzewo ma n możliwości na każdym poziomie, a łączna liczba liści wynosi n!. Kombinacje — używają indeksu początkowego, aby wymusić kolejność, a liczba liści wynosi C(n,k). Combination Sum — nie przesuwa indeksu początkowego, aby umożliwić ponowne użycie, i przycina gałęzie na podstawie wartości target. Przyporządkowanie nowego problemu do jednej z tych trzech postaci od razu wskazuje właściwy szablon.
# 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}')Złożoność i wskazówki na rozmowę kwalifikacyjną
Złożoność czasowa wyliczania wynosi: Permutations O(n × n!), Combinations O(k × C(n,k)), Combination Sum O(n^(T/min_val)). Złożoność pamięciowa to O(n) dla głębokości rekurencji oraz O(output) dla wyników. Kluczowe wskazówki: (1) Zawsze należy ustalić, czy kolejność ma znaczenie (permutacja czy kombinacja). (2) Należy wspomnieć o obsłudze duplikatów, zanim rekruter o to zapyta. (3) Zawsze należy wyraźnie podać warunek przycinania. (4) W przypadku dużego n należy zauważyć, że same dane wyjściowe mają rozmiar wykładniczy — algorytm jest optymalny dla tego zadania.
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)'Szybki sprawdzian
Proszę sprawdzić swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: permutacje używają tablicy used i nie korzystają z indeksu początkowego, generując n! ułożeń, kombinacje używają indeksu początkowego przesuwanego w celu uniknięcia ponownego użycia, generując C(n,k) wyborów, a duplikaty w obu problemach obsługuje się przez sortowanie i pomijanie powtarzających się wartości na tym samym poziomie rekurencji. Następnie zastosujemy backtracking do problemu N-Queens i poznamy propagację ograniczeń.
Często zadawane pytania
Czy lekcja „Permutacje i kombinacje” jest bezpłatna?
Tak — pełny tekst „Permutacje i kombinacje” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Permutacje i kombinacje”?
Wyliczać wszystkie permutacje listy — zarówno z powtarzającymi się elementami, jak i bez nich — oraz generować wszystkie k-kombinacje i warianty sumy kombinacji Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Permutacje i kombinacje”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Szablon backtrackingu: wybierz, zbadaj, cofnij wybór
- Podzbiory i zbiór potęgowy
- Permutacje i kombinacje
- Problem N hetmanów i propagacja ograniczeń