Tạo tất cả hoán vị 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 số thứ tự hoặc một dãy nào đó và nếu tập hợp đã được sắp xếp theo thứ tự thì việc sắp xếp lại (sắp xếp lại) các phần tử của nó được gọi là hoán vị. Dưới đây là một số trong số chúng,

Phương pháp 1

Python đi kèm với mô-đun dành riêng cho các hoán vị và kết hợp được gọi là itertools.

Trước tiên hãy nhập mô-đun

>>> import itertools
>>>

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

Permutation (order matters):
>>> 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)]

Kế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

Dưới đây là cách triển khai trên danh sách mà không cần 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)

đầu ra

[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

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])

đầu ra

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