Tạo tất cả hoán vị (permutation) của một tập hợp trong Python

Trong toán học, việc sắp xếp tất cả các thành viên của một tập hợp thành một trình tự hoặc chuỗi nào đó và nếu tập hợp đã được sắp xếp, việc sắp xếp lại (reordering) các phần tử của nó được gọi là hoán vị (permutation). Chúng ta có thể tạo hoán vị bằng các kỹ thuật khác nhau. Dưới đây là một số phương pháp:

Phương pháp 1: Sử dụng module itertools

Python đi kèm với module chuyên dụng cho hoán vị và tổ hợp gọi là itertools.

Nhập module trước

>>> import itertools
>>>

Hàm permutations cho phép chúng ta lấy hoán vị của N giá trị trong một danh sách, nơi thứ tự quan trọng. Ví dụ, chọn N = 2 giá trị với [1,2,3,4] được thực hiện như sau:

Permutation (thứ tự quan trọng):
>>> print(list(itertools.permutations([1,2,3,4],2)))
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

Combination (Tổ hợp - thứ tự không quan trọng)

>>> print(list(itertools.combinations('1234', 2)))
[('1', '2'), ('1', '3'), ('1', '4'), ('2', '3'), ('2', '4'), ('3', '4')]

Phương pháp 2: Triển khai trên danh sách mà không tạo danh sách trung gian mới

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p
        for i in range(low + 1, len(xs)):
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3]):
    print(p)

Kết quả

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

Phương pháp 3: Sử dụng Đệ quy (Recursion)

import copy

def perm(prefix, rest):
    for e in rest:
        new_rest = copy.copy(rest)
        new_prefix = copy.copy(prefix)
        new_prefix.append(e)
        new_rest.remove(e)
        if len(new_rest) == 0:
            print(new_prefix + new_rest)
            continue
        perm(new_prefix, new_rest)

perm([], [1, 2, 3])

Kết quả

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