Viết chương trình python để in các hoán vị duy nhất của một số đã cho

Phạm vi của Điều

• Chúng ta sẽ tìm hiểu về hoán vị và tổ hợp cùng với ý nghĩa của chúng
• Chúng tôi sẽ đề cập đến cách tìm hoán vị trong Python bằng cách sử dụng cả đệ quy và itertools
• Chúng ta sẽ tìm hoán vị của chuỗi và số cũng như hoán vị có độ dài cố định bằng cách sử dụng itertools trong Python
• Chúng tôi sẽ sử dụng itertools để tìm tất cả các kết hợp chuỗi và số, với độ dài cần thiết
• Chúng tôi cũng sẽ bao gồm các kết hợp với sự lặp lại và thay thế

Giới thiệu về hoán vị trong Python

Hãy chơi một trò chơi. mặt cười. Cố gắng hình thành càng nhiều từ càng tốt bằng cách sử dụng tất cả các chữ cái. O, T, P. (Gợi ý. Có 3 từ) Chà, tôi chỉ có thể đoán được hai từ. NỒI và HÀNG ĐẦU. thất vọng. Làm thế nào để tìm ra thứ ba?

Ta có thể dùng brute force để sắp xếp các chữ cái trong từ OTP vào mọi vị trí có thể. Chúng ta có thể tìm thấy tất cả các từ bằng cách sử dụng các cách sắp xếp khác nhau của bốn chữ cái. Đây là những gì chúng ta gọi là hoán vị

Hoán vị đề cập đến các cách khác nhau trong đó một tập hợp các đối tượng nhất định có thể được sắp xếp. Ví dụ, trong bài toán của chúng ta, chúng ta có thể sắp xếp ba chữ cái theo 6 cách sau

Chúng ta có thể tìm các từ khác nhau có thể được tạo ra từ bộ ba chữ cái {O, T, P} bằng cách sử dụng hoán vị và lọc ra các từ có nghĩa. Điều này mang lại cho chúng tôi 3 từ. LỰA CHỌN, HÀNG ĐẦU và POT

Bây giờ tôi muốn chơi trò chơi theo đội 3 người và cần chọn 2 trong số 4 người bạn của tôi để thành lập đội của mình. Hãy nhớ rằng thứ tự tôi chọn chúng không tạo ra bất kỳ sự khác biệt nào. Đây được gọi là sự kết hợp. Kết hợp là cách chọn k mục từ một tập hợp gồm n mục (k <= n), trong đó thứ tự lựa chọn không quan trọng. Sơ đồ dưới đây thể hiện 6 cách mà tôi có thể chọn 2 trong số 4 người bạn

6 cách hoặc kết hợp từ một bộ bốn người bạn a, b, c và d là. (a, b), (a, c), (a, d), (b, c) (b, d), (c, d). Bây giờ chúng ta đã hiểu tầm quan trọng của hoán vị và tổ hợp, hãy triển khai chúng bằng Python

Nhập thư viện cần thiết

Chúng tôi có các phương thức cụ thể trong thư viện itertools của Python để tìm các hoán vị và kết hợp cho một nhóm đối tượng nhất định. Để sử dụng chúng, đầu tiên chúng ta nhập thư viện itertools như sau

Hãy cho chúng tôi xem cách chúng tôi có thể sử dụng các phương pháp được xác định trước để tính toán các hoán vị và tổ hợp của một tập hợp các đối tượng, trong các phần tiếp theo

Hoán vị trong Python là gì?

Hãy để chúng tôi lấy một ví dụ về trò chơi tạo từ mà chúng tôi đã thảo luận trong phần Giới thiệu. Làm cách nào chúng ta có thể sử dụng Python để tạo hoán vị của các chữ cái O, T, P

Có hai cách tạo hoán vị trong Python

1. Hoán vị của một chuỗi sử dụng đệ quy

Trước khi tìm hiểu về phương thức được xác định trước trong thư viện itertools, trước tiên chúng ta hãy xem hậu trường. Chúng tôi sẽ tìm các hoán vị của một chuỗi đã cho từ đầu, sử dụng đệ quy

bước

• Trước tiên chúng tôi xác định điều kiện cơ sở cho đệ quy. Nếu i bằng độ dài của chuỗi, chúng ta nối mảng các chữ cái và in ra từ đó
• Trong phương thức *findPermutations()*, chúng ta hoán đổi vị trí của các chữ cái thứ i và thứ j trong từ và truyền lại cho hàm
• Quá trình này được lặp lại cho đến khi đạt được độ dài tối đa của từ. Mỗi từ được lưu trữ dưới dạng hoán vị của chuỗi gốc

THÍ DỤ

def findPermutations(string, i = 0):
    if i == len(string):   	 
        print("".join(string))

    for j in range(i, len(string)):
        words = [c for c in string]
        words[i], words[j] = words[j], words[i]
        findPermutations(words, i + 1)

findPermutations('OTP')
đầu ra
Chúng tôi sử dụng phương thức hoán vị () được xác định trước trong thư viện itertools để nhận tất cả các hoán vị của một tập hợp đối tượng nhất định
CÚ PHÁP
hoán vị ('OTP')
Nếu chúng ta in lệnh trên, chúng ta sẽ nhận được vị trí đối tượng của đối tượng itertools như sau
Để có được tất cả các hoán vị của từ OTP, chúng ta cần lặp qua từ đó bằng vòng lặp for. Mỗi hoán vị riêng biệt được trả về dưới dạng một tuple
THÔNG SỐ
Phương thức permutations() nhận 2 tham số
Đối tượng - Đối tượng có hoán vị chúng ta phải tìm
Độ dài (tùy chọn) - Độ dài mong muốn của mỗi hoán vị. Nó lấy giá trị mặc định của chiều dài đối tượng

THÍ DỤ

Để in các hoán vị dưới dạng từ, chúng ta có thể nối các bộ như trong đoạn mã dưới đây

from itertools import permutations

perm = permutations('OTP')
for p in perm:
    print(''.join(p))
đầu ra
Giải trình
Ở dòng 1, chúng ta nhập phương thức permutations() từ thư viện itertools
Chúng tôi chuyển chuỗi 'OTP' làm đầu vào cho phương thức. Các hoán vị khác nhau được lưu trữ dưới dạng danh sách các bộ trong perm
Trong các dòng 4-5, chúng tôi lặp qua danh sách các bộ dữ liệu và in từng hoán vị bằng cách nối bộ ký tự

Hoán vị của các số

Tương tự như tìm hoán vị của một chuỗi, chúng ta cũng có thể tìm hoán vị của một tập hợp số đã cho bằng cách chuyển chúng dưới dạng một lần lặp. Chúng tôi sử dụng cùng một phương thức hoán vị () và chuyển danh sách các số dưới dạng tham số

THÍ DỤ

from itertools import permutations

list = [1, 4, 9]
perm = permutations(list)

for p in perm:
    print(p)
đầu ra
(1, 4, 9)
(1, 9, 4)
(4, 1, 9)
(4, 9, 1)
(9, 1, 4)
(9, 4, 1)
Giải trình
Đoạn mã trên tương tự như tìm hoán vị của một từ. Sự khác biệt duy nhất là cách chúng tôi chuyển đầu vào - dưới dạng danh sách các số. Phương thức hoán vị () trả về các cách sắp xếp khác nhau có thể có ở dạng bộ dữ liệu

Hoán vị của một độ dài cố định

Giả sử bây giờ chúng ta cần tìm tất cả các từ có hai chữ cái có thể được tạo bằng chuỗi ban đầu 'OTP'. Đã đến lúc sử dụng tham số độ dài tùy chọn của phương thức permutations(). Chúng tôi có thể chỉ định độ dài mong muốn của mỗi hoán vị bằng cách chuyển nó vào phương thức của chúng tôi

THÍ DỤ

from itertools import permutations

perm = permutations('OTP', 2)
for p in perm:
    print(''.join(p))
đầu ra
Giải trình
Chúng tôi chuyển độ dài mong muốn của hoán vị (ở đây, 2) làm tham số thứ hai của phương thức hoán vị(). Điều này in tất cả các cách sắp xếp có thể có của từ 'OTP' có độ dài là 2. Tương tự, chúng ta có thể chỉ định độ dài làm tham số thứ hai để nhận tất cả các hoán vị của một danh sách các số

Kết hợp trong Python là gì?

Kết hợp là những cách mà chúng ta có thể chọn k mục từ danh sách n mục, bất kể thứ tự lựa chọn. Ta hãy xét bài toán cần chọn 2 trong 4 bạn để lập đội. Làm cách nào chúng tôi có thể tạo tất cả các kết hợp của 2 người bạn từ nhóm bạn bè của chúng tôi (a, b, c, d)?

CÚ PHÁP

kết hợp (['a', 'b', 'c', 'd'], 2)

Nếu chúng ta in lệnh trên, chúng ta sẽ nhận được vị trí đối tượng của đối tượng itertools như sau

THÔNG SỐ

THÍ DỤ

Để có được tất cả các kết hợp của 2 người bạn từ danh sách bạn bè của chúng ta ['a', 'b', 'c', 'd'], chúng ta cần lặp qua phương thức kết hợp() bằng vòng lặp for. Đầu ra sẽ là một danh sách các bộ dữ liệu, trong đó mỗi bộ dữ liệu là một sự kết hợp duy nhất. Dưới đây là cách mã và đầu ra sẽ như thế nào

from itertools import combinations

friends = ['a', 'b', 'c', 'd']
comb = combinations(friends, 2)

for c in comb:
	print (c)
đầu ra
('a', 'b')
('a', 'c')
('a', 'd')
('b', 'c')
('b', 'd')
('c', 'd')
Giải trình
Dòng 1 nhập phương thức kết hợp () từ thư viện itertools
Ở dòng 4, chúng ta truyền hai tham số cho phương thức
Danh sách bạn bè mà chúng tôi muốn kết hợp
Độ dài mong muốn của mỗi kết hợp (ở đây, 2)
Trong các dòng 6-7, chúng tôi lặp qua các kết hợp khác nhau được lưu trữ dưới dạng bộ dữ liệu và in chúng

Sự kết hợp của các số

Tương tự như tìm các tổ hợp của một danh sách các chuỗi, chúng ta cũng có thể tìm các tổ hợp của một tập hợp số đã cho. Chúng tôi sử dụng cùng một phương thức kết hợp () và chuyển danh sách các số dưới dạng tham số

THÍ DỤ

from itertools import combinations

list = [1, 4, 9]
comb = combinations(list, 2)

for c in comb:
    print(c)
đầu ra
________số 8_______
Giải trình
Đoạn mã trên tương tự như việc tìm các tổ hợp của một từ hoặc một danh sách các chuỗi. Chúng tôi chuyển danh sách các số và độ dài mong muốn cho phương thức kết hợp (). Sau đó, nó trả về các kết hợp khác nhau có thể có ở dạng bộ dữ liệu

Tổ hợp các số lặp lại

Điều gì xảy ra nếu có các bản sao trong danh sách mà chúng tôi muốn kết hợp? . Điều này là do các kết hợp được tạo dựa trên các chỉ số hoặc vị trí, không dựa trên các giá trị thực tế. Nếu không có sự lặp lại, chúng tôi sẽ nhận được tất cả các kết hợp duy nhất, không giống như trong trường hợp này

THÍ DỤ

from itertools import combinations

list = [1, 4, 4, 1, 9]
comb = combinations(list, 2)

for c in comb:
    print(c)
đầu ra
from itertools import permutations

perm = permutations('OTP')
for p in perm:
    print(''.join(p))
0
Giải trình
Trong đoạn mã trên, chúng tôi đã chuyển một danh sách số với các số 1 và 4 được lặp lại hai lần. Đây là lý do tại sao một số kết hợp như (1,4), (1,9), (4,1) và (4,9) được tạo nhiều lần

Kết hợp với thay thế

Bây giờ chúng ta hãy xem xét một tình huống mà chúng ta muốn cho phép kết hợp một phần tử với chính nó. Điều này có nghĩa là các phần tử riêng lẻ có thể được lặp lại nhiều lần, ngay cả khi không có sự lặp lại nào trong lần lặp đầu vào ban đầu. Chúng tôi sử dụng phương thức tổ hợp_with_replacement() có trong thư viện itertools để đạt được điều này

THÍ DỤ

from itertools import permutations

perm = permutations('OTP')
for p in perm:
    print(''.join(p))
1
đầu ra
from itertools import permutations

perm = permutations('OTP')
for p in perm:
    print(''.join(p))
2
Giải trình
Khi chúng tôi so sánh kết quả này với kết quả chúng tôi nhận được bằng cách sử dụng phương thức kết hợp (), chúng tôi tìm thấy ba kết quả bổ sung. (1,1), (4,4), (9,9). Điều này là do khi chúng ta chọn một phần tử từ danh sách, phương thức tổ hợp_with_replacement() sẽ thay thế phần tử đó bằng cùng một giá trị để nhận các kết hợp với chính nó