Hoán vị và Tổ hợp (Permutation & Combination) trong Python

Module itertools cung cấp hàm tạo hoán vị và tổ hợp hiệu quả, bộ nhớ thấp (iterator).

Import

import itertools
# hoặc
from itertools import permutations, combinations, combinations_with_replacement

Permutations (Hoán vị) - Thứ tự quan trọng

Số hoán vị của n phần tử lấy r: P(n, r) = n! / (n-r)!

Ví dụ 1: Tất cả hoán vị của 3 phần tử

from itertools import permutations

seq = permutations(['a', 'b', 'c'])
for p in seq:
    print(p)

('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

Ví dụ 2: Hoán vị độ dài r=2 từ 6 phần tử

seq = permutations(['p', 'y', 't', 'h', 'o', 'n'], 2)
for p in seq:
    print(p)

('p', 'y') ('p', 't') ('p', 'h') ('p', 'o') ('p', 'n')
('y', 'p') ('y', 't') ('y', 'h') ('y', 'o') ('y', 'n')
('t', 'p') ('t', 'y') ('t', 'h') ('t', 'o') ('t', 'n')
('h', 'p') ('h', 'y') ('h', 't') ('h', 'o') ('h', 'n')
('o', 'p') ('o', 'y') ('o', 't') ('o', 'h') ('o', 'n')
('n', 'p') ('n', 'y') ('n', 't') ('n', 'h') ('n', 'o')

Combinations (Tổ hợp) - Thứ tự KHÔNG quan trọng

Số tổ hợp của n phần tử lấy r: C(n, r) = n! / (r! * (n-r)!)

Ví dụ 1: Tổ hợp r=5 từ 6 phần tử

from itertools import combinations

combi = combinations(['p', 'y', 't', 'h', 'o', 'n'], 5)
for c in combi:
    print(c)

('p', 'y', 't', 'h', 'o')
('p', 'y', 't', 'h', 'n')
('p', 'y', 't', 'o', 'n')
('p', 'y', 'h', 'o', 'n')
('p', 't', 'h', 'o', 'n')
('y', 't', 'h', 'o', 'n')

Ví dụ 2: Combinations with replacement (Có lặp lại)

from itertools import combinations_with_replacement

combi = combinations_with_replacement(['p', 'y', 't', 'h', 'o', 'n'], 2)
for c in combi:
    print(c)

('p', 'p') ('p', 'y') ('p', 't') ('p', 'h') ('p', 'o') ('p', 'n')
('y', 'y') ('y', 't') ('y', 'h') ('y', 'o') ('y', 'n')
('t', 't') ('t', 'h') ('t', 'o') ('t', 'n')
('h', 'h') ('h', 'o') ('h', 'n')
('o', 'o') ('o', 'n')
('n', 'n')

Tóm tắt

Lưu ý hiệu năng

• Trả về iterator -> lười (lazy), tiết kiệm bộ nhớ.
• Chuyển list nếu cần: list(permutations(...)) (cẩn thận O(n!)).
• Dùng math.comb(n, k), math.perm(n, k) (Python 3.8+) để chỉ tính số lượng.