Trong toán học, khái niệm hoán vị liên quan đến hành động 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 thứ tự nào đó, hoặc nếu tập hợp đã được sắp xếp, sắp xếp lại [sắp xếp lại] các phần tử của nó, một quá trình được gọi là hoán vị. Chúng khác với các kết hợp, là các lựa chọn của một số thành viên của một tập hợp mà thứ tự bị bỏ qua
Trong hình ảnh sau, mỗi hàng trong số sáu hàng là một hoán vị khác nhau của ba quả bóng riêng biệt
Giải pháp mẫu. -
Mã Python
def permute_string[str]:
if len[str] == 0:
return ['']
prev_list = permute_string[str[1:len[str]]]
next_list = []
for i in range[0,len[prev_list]]:
for j in range[0,len[str]]:
new_str = prev_list[i][0:j]+str[0]+prev_list[i][j:len[str]-1]
if new_str not in next_list:
next_list.append[new_str]
return next_list
print[permute_string['ABCD']];
Đầu ra mẫu
['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB', 'CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC ', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Sơ đồ
Trực quan hóa việc thực thi mã Python
Công cụ sau đây trực quan hóa những gì máy tính đang làm từng bước khi nó thực thi chương trình nói trên
Trình chỉnh sửa mã Python
Có một cách khác để giải quyết giải pháp này?
Trước. Viết chương trình Python trả về tổng tất cả các ước của một số
Kế tiếp. Viết chương trình Python để in ra n số may mắn đầu tiên
Mức độ khó của bài tập này là gì?
Dễ dàng trung bình khóKiểm tra kỹ năng Lập trình của bạn với bài kiểm tra của w3resource
Theo dõi chúng tôi trên Facebook và Twitter để cập nhật thông tin mới nhất.
con trăn. Lời khuyên trong ngày
getsizeof[]
Phương thức Getsizeof[] từ thư viện sys của Python sẽ cho bạn biết kích thước của một đối tượng Python trong bộ nhớ
import sys x="Australia" y=sys.getsizeof[x] print[y]
đầu ra
58
Kết quả tính bằng byte
Getsizeof[] sẽ cung cấp kích thước của bất kỳ đối tượng Python nào. Đối tượng phạm vi, đối tượng byte, đối tượng đảo ngược, đối tượng danh sách, đối tượng từ điển, danh sách tiếp tục
Chương trình Python để in tất cả các hoán vị của một chuỗi đã cho;
Trước khi chia sẻ với các bạn chương trình tìm tất cả các hoán vị của chuỗi đã cho trong python. Bạn nên biết về mô-đun python itertools, vì mô-đun này sẽ giúp tìm tất cả các hoán vị của chuỗi đã cho
hoán vị. - Như chúng ta đã biết, hoán vị là cách sắp xếp các phần tử của một nhóm hoặc một tập hợp theo một trật tự hoặc trình tự xác định để tạo thành một nhóm riêng
Trong hướng dẫn này, bạn sẽ học cách sử dụng Python để tìm tất cả các hoán vị của một chuỗi, bao gồm sử dụng itertools, đệ quy và vòng lặp Python for. Bạn cũng sẽ học cách tìm tất cả các kết hợp của một chuỗi khi cho phép thay thế các chữ cái riêng lẻ
Nhưng một hoán vị là gì? . Vì vậy, ví dụ, chuỗi abc cũng có thể được viết là ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Câu trả lời nhanh. Người dùng Itertools để tìm tất cả các hoán vị của một chuỗi
Mục lục
Hoán vị của một chuỗi là gì?
Hoán vị của một chuỗi đề cập đến tất cả các thứ tự khác nhau mà một chuỗi có thể thực hiện. Ví dụ, hãy xem một chuỗi có ba chữ cái. 'abc'. Khi chúng tôi tìm thấy tất cả các hoán vị của chuỗi này, chúng tôi sẽ trả về danh sách sau. ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. Chúng ta có thể thấy ở đây, rằng chúng ta có một danh sách chứa sáu mục
Chúng ta thực sự có thể tính toán số lượng hoán vị mà một chuỗi sẽ có đối với bất kỳ cường độ độ dài nào, bằng cách tính giai thừa của độ dài của nó. Vì vậy, trong ví dụ của chúng tôi về 'abc', chúng tôi sẽ tính giá trị của 3!, mà thực tế đánh giá là
# Getting all permutations of a string using recursion in Python
a_string = 'abc'
def get_permutation[some_string, idx=0]:
if idx == len[some_string] - 1:
print["".join[some_string]]
for j in range[idx, len[some_string]]:
words_list = [c for c in some_string]
words_list[idx], words_list[j] = words_list[j], words_list[idx]
get_permutation[words_list, idx + 1]
permutations = get_permutation[a_string]
print[permutations]
# Returns: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']Bây giờ bạn đã hiểu ý nghĩa của việc tạo tất cả các kết hợp của một chuỗi trong Python, hãy xem cách chúng ta có thể dễ dàng tạo các hoán vị khác nhau của một chuỗi
Sử dụng Itertools trong Python để tìm tất cả các hoán vị của chuỗi
Itertools là một công cụ Python tích hợp, tuyệt vời cho phép bạn thực hiện dễ dàng các vấn đề liên quan đến iterables. Dù bạn có tin hay không, các chuỗi trong Python là các đối tượng có thể lặp lại. Vì điều này, chúng ta có thể dễ dàng lặp lại các chuỗi của mình bằng thư viện itertools
Trên thực tế, thư viện itertools có chức năng gọi là
# Getting all permutations of a string using recursion in Python
a_string = 'abc'
def get_permutation[some_string, idx=0]:
if idx == len[some_string] - 1:
print["".join[some_string]]
for j in range[idx, len[some_string]]:
words_list = [c for c in some_string]
words_list[idx], words_list[j] = words_list[j], words_list[idx]
get_permutation[words_list, idx + 1]
permutations = get_permutation[a_string]
print[permutations]
# Returns: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']Hãy xem chuỗi ví dụ của chúng tôi và cách chúng tôi có thể sử dụng thư viện itertools để tính toán các hoán vị của nó
import itertools
a_string = 'abc'
string_permutations = itertools.permutations[a_string]
string_permutations = list[string_permutations]
string_permutations = [''.join[permutation] for permutation in string_permutations]
print[string_permutations]
# Returns: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']Hãy xem những gì chúng tôi đã làm ở đây
- Chúng tôi đã nhập thư viện itertools
- Chúng tôi đã tải chuỗi của mình và gán nó cho biến
3# Getting all permutations of a string using recursion in Python a_string = 'abc' def get_permutation[some_string, idx=0]: if idx == len[some_string] - 1: print["".join[some_string]] for j in range[idx, len[some_string]]: words_list = [c for c in some_string] words_list[idx], words_list[j] = words_list[j], words_list[idx] get_permutation[words_list, idx + 1] permutations = get_permutation[a_string] print[permutations] # Returns: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] - Sau đó, chúng tôi đã sử dụng hàm
4 để tạo đối tượng itertools# Getting all permutations of a string using recursion in Python a_string = 'abc' def get_permutation[some_string, idx=0]: if idx == len[some_string] - 1: print["".join[some_string]] for j in range[idx, len[some_string]]: words_list = [c for c in some_string] words_list[idx], words_list[j] = words_list[j], words_list[idx] get_permutation[words_list, idx + 1] permutations = get_permutation[a_string] print[permutations] # Returns: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] - Chúng tôi đã biến đối tượng này thành một danh sách, danh sách này trả về một danh sách các bộ chứa các hoán vị của chúng tôi
- Cuối cùng, chúng tôi đã sử dụng cách hiểu danh sách để kết hợp các hoán vị của chúng tôi thành các chuỗi riêng lẻ
Trong phần tiếp theo, bạn sẽ học cách sử dụng đệ quy để tìm các tổ hợp của một chuỗi trong Python
Bạn muốn tìm hiểu thêm về cách hiểu danh sách Python? . Thêm một người học trực quan, hãy xem hướng dẫn YouTube của tôi tại đây
Sử dụng đệ quy trong Python để tìm tất cả các hoán vị của chuỗi
Khái niệm chúng ta sẽ sử dụng trong đệ quy để tạo hoán vị được gọi là quay lui. Ý tưởng là chúng tôi quay lại cho từng kết hợp có thể tồn tại
Chúng ta hãy xem phương thức đệ quy này hoạt động như thế nào để giúp tìm tất cả các kết hợp của một chuỗi trong Python
# Getting all permutations of a string using recursion in Python
a_string = 'abc'
def get_permutation[some_string, idx=0]:
if idx == len[some_string] - 1:
print["".join[some_string]]
for j in range[idx, len[some_string]]:
words_list = [c for c in some_string]
words_list[idx], words_list[j] = words_list[j], words_list[idx]
get_permutation[words_list, idx + 1]
permutations = get_permutation[a_string]
print[permutations]
# Returns: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']Chúng ta có thể thấy rằng điều này trả về giống như trên. Tuy nhiên, việc theo dõi đối với người dùng Python mới bắt đầu sẽ kém trực quan hơn một chút, vì vậy có lẽ sử dụng phương thức itertools có thể được ưu tiên hơn để dễ đọc. Tuy nhiên, phương pháp này hữu ích khi bạn không thể sử dụng itertools vì lý do nào đó
Bạn muốn tìm hiểu cách sử dụng hàm
# Getting all permutations of a string using recursion in Python
a_string = 'abc'
def get_permutation[some_string, idx=0]:
if idx == len[some_string] - 1:
print["".join[some_string]]
for j in range[idx, len[some_string]]:
words_list = [c for c in some_string]
words_list[idx], words_list[j] = words_list[j], words_list[idx]
get_permutation[words_list, idx + 1]
permutations = get_permutation[a_string]
print[permutations]
# Returns: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']Hoán vị với sự lặp lại của một chuỗi trong Python
Trong các ví dụ trên, chúng tôi đã sử dụng Python để tìm tất cả các kết hợp của một chuỗi mà không cần lặp lại. Trong phần này, bạn sẽ học cách sử dụng Python để lấy tất cả các hoán vị của một chuỗi có lặp lại
Điều này có thể dễ dàng thực hiện bằng cách sử dụng vòng lặp Python for
Hãy xem một ví dụ, sử dụng cùng một chuỗi mà chúng ta đã sử dụng trước đó, 'abc'
# Use Python to get all combinations of a string with repetition
a_string = 'abc'
final_list = [[]]
length = len[a_string]
groups = [list[a_string]] * length
for i in groups:
final_list = [x+[y] for x in final_list for y in i]
permutations = [''.join[item] for item in final_list]
print[permutations]
# Returns ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']Trong đoạn mã trên, chúng tôi sử dụng vòng lặp for và khả năng hiểu danh sách để trả về tất cả các kết hợp của chuỗi Python có lặp lại
Đoạn mã trên có thể trở nên khá tốn tài nguyên. Chúng ta cũng có thể thấy ở đây rằng chúng ta có nhiều kết hợp hơn nhiều lần khi chúng ta sử dụng phép lặp so với khi chúng ta không sử dụng.
Bạn muốn tìm hiểu thêm về các vòng lặp Python? . Thay vào đó, bạn muốn xem một video?
Phần kết luận
Trong bài đăng này, bạn đã học cách sử dụng Python để tạo danh sách tất cả các hoán vị của một chuỗi. Bạn đã học cách làm điều này bằng cách sử dụng thư viện itertools phổ biến cũng như sử dụng đệ quy. Sau đó, bạn đã học cách sử dụng vòng lặp for trong Python để tạo danh sách tất cả các kết hợp của một chuỗi khi cho phép lặp lại