Hoán vị Python đệ quy

Question

Ví dụ. số cách mà các ký tự từ yup có thể được chọn là yup, ypu, uyp, upy, puy,

yup
ypu
uyp
upy
puy
pyu
None

0 và không chọn bất kỳ ký tự nào

Nội dung chính Show

ví dụ 1. Sử dụng đệ quy
ví dụ 2. Sử dụng itertools
Thuật ngữ của lý thuyết tập hợp
Tìm tất cả các hoán vị mà không cần lặp lại. Biểu đồ chỗ ngồi trong đám cưới
Nhận hoán vị với các vòng lặp lồng nhau. Một cách tiếp cận kém lý tưởng
Hoán vị với sự lặp lại. Trình bẻ khóa mật khẩu
Nhận kết hợp K với đệ quy
Nhận tất cả các kết hợp của dấu ngoặc đơn cân bằng
Bộ nguồn. Tìm tất cả các tập con của một tập hợp
Bản tóm tắt
Có chức năng hoán vị trong Python không?
Thuật toán nào tìm thấy tất cả các hoán vị?
Các tham số cho hoán vị trong Python là gì?
Hoán vị của ABC trong Python là gì?

Chúng tôi sẽ thực hiện tương tự trong các ví dụ sau

ví dụ 1. Sử dụng đệ quy

def get_permutation(string, i=0):

    if i == len(string):   	 
        print("".join(string))

    for j in range(i, len(string)):

        words = [c for c in string]
   
        # swap
        words[i], words[j] = words[j], words[i]
   	 
        get_permutation(words, i + 1)

print(get_permutation('yup'))

đầu ra

yup
ypu
uyp
upy
puy
pyu
None

Trong ví dụ này, đệ quy được sử dụng để tìm các hoán vị của một chuỗi yup

Điều kiện if in ra
```
yup
ypu
uyp
upy
puy
pyu
None
```
2 được truyền dưới dạng đối số nếu nó bằng độ dài của
```
yup
ypu
uyp
upy
puy
pyu
None
```
3
Trong mỗi lần lặp của vòng lặp for, mỗi ký tự của yup được lưu trữ trong
```
yup
ypu
uyp
upy
puy
pyu
None
```
5
Các thành phần của từ được hoán đổi. Bằng cách này, chúng tôi đạt được tất cả các kết hợp ký tự khác nhau
Quá trình này tiếp tục cho đến khi đạt được chiều dài tối đa

ví dụ 2. Sử dụng itertools

from itertools import permutations

words = [''.join(p) for p in permutations('pro')]

print(words)

đầu ra

['pro', 'por', 'rpo', 'rop', 'opr', 'orp']

Sử dụng các hoán vị từ mô-đun

yup
ypu
uyp
upy
puy
pyu
None

6, chúng ta có thể tìm thấy các hoán vị của một chuỗi

Các bài toán liên quan đến hoán vị và tổ hợp đặc biệt phù hợp với đệ quy. Đây là những điều phổ biến trong lý thuyết tập hợp, một nhánh của logic toán học liên quan đến việc lựa chọn, sắp xếp và thao tác các tập hợp đối tượng

Xử lý các tập hợp nhỏ trong trí nhớ ngắn hạn của chúng ta rất đơn giản. Chúng ta có thể dễ dàng đưa ra mọi thứ tự có thể (nghĩa là hoán vị) hoặc kết hợp của một bộ ba hoặc bốn đối tượng. Đặt hàng và kết hợp các mục trong một bộ lớn hơn đòi hỏi quy trình tương tự nhưng nhanh chóng trở thành nhiệm vụ bất khả thi đối với bộ não con người chúng ta. Tại thời điểm đó, việc sử dụng máy tính để xử lý vụ nổ tổ hợp xảy ra khi chúng ta thêm nhiều đối tượng vào một tập hợp sẽ trở nên thiết thực.

Về cơ bản, việc tính toán các hoán vị và tổ hợp của các nhóm lớn liên quan đến việc tính toán các hoán vị và tổ hợp của các nhóm nhỏ hơn. Điều này làm cho các tính toán này phù hợp với đệ quy. Trong chương này, chúng ta sẽ xem xét các thuật toán đệ quy để tạo ra tất cả các hoán vị và tổ hợp ký tự có thể có trong một chuỗi. Chúng tôi sẽ mở rộng điều này để tạo ra tất cả các kết hợp có thể có của dấu ngoặc đơn cân bằng (thứ tự của dấu ngoặc đơn mở khớp chính xác với dấu ngoặc đơn đóng). Và cuối cùng, chúng ta sẽ tính lũy thừa của một tập hợp—tức là tập hợp tất cả các tập hợp con có thể có của một tập hợp

Nhiều hàm đệ quy trong chương này có một đối số tên là

8. Điều này không được sử dụng bởi các thuật toán đệ quy thực tế; . Thụt đầu dòng được tăng thêm một khoảng trắng cho mỗi lệnh gọi đệ quy và được hiển thị trong đầu ra gỡ lỗi dưới dạng các khoảng thời gian để dễ dàng đếm mức độ thụt đầu dòng

Thuật ngữ của lý thuyết tập hợp

Chương này không đề cập đến lý thuyết tập hợp một cách hoàn chỉnh như sách giáo khoa toán học hoặc khoa học máy tính. Nhưng nó bao quát đủ để biện minh cho việc bắt đầu bằng việc giải thích thuật ngữ cơ bản của chuyên ngành, vì làm như vậy sẽ giúp phần còn lại của chương này dễ hiểu hơn. Một tập hợp là một tập hợp các đối tượng duy nhất, được gọi là các phần tử hoặc thành viên. Ví dụ: các chữ cái A, B và C tạo thành một bộ ba chữ cái. Trong toán học (và trong cú pháp mã Python), các tập hợp được viết bên trong dấu ngoặc nhọn, với các đối tượng được phân tách bằng dấu phẩy. {A, B, C}

Thứ tự không quan trọng đối với một bộ; . Các bộ có các phần tử riêng biệt, nghĩa là không có phần tử trùng lặp. {A, C, A, B} đã lặp lại As và do đó không phải là một tập hợp

Một tập hợp là tập hợp con của một tập hợp khác nếu nó chỉ có các phần tử của tập hợp kia. Ví dụ: {A, C} và {B, C} đều là tập con của {A, B, C} nhưng {A, C, D} không phải là tập con của nó. Ngược lại, {A, B, C} là tập hợp siêu của {A, C} và cả {B, C} vì nó chứa tất cả các phần tử của chúng. Tập hợp rỗng { } là tập hợp không có phần tử nào. Các tập hợp rỗng được coi là tập hợp con của mọi tập hợp có thể

Một tập hợp con cũng có thể bao gồm tất cả các phần tử của tập hợp kia. Ví dụ: {A, B, C} là tập con của {A, B, C}. Nhưng một tập hợp con thích hợp, hoặc tập hợp con nghiêm ngặt, là một tập hợp con không có tất cả các phần tử của tập hợp. Không có tập hợp nào là tập hợp con của chính nó. vì vậy {A, B, C} là tập con nhưng không phải là tập con thực của {A, B, C}. Tất cả các tập con khác là tập con thích hợp. hiển thị biểu diễn đồ họa của tập hợp {A, B, C} và một số tập hợp con của nó

Hình 6-1. Tập hợp {A, B, C} trong các đường đứt nét và một số tập hợp con của nó {A, B, C}, {A, C} và { } trong các đường liền nét. Các vòng tròn đại diện cho các tập hợp và các chữ cái đại diện cho các phần tử

Một hoán vị của một tập hợp là một thứ tự cụ thể của tất cả các phần tử trong tập hợp. Ví dụ: tập hợp {A, B, C} có sáu hoán vị. ABC, ACB, BAC, BCA, CAB và CBA. Chúng tôi gọi đây là các hoán vị không lặp lại hoặc hoán vị không thay thế, bởi vì mỗi phần tử không xuất hiện trong hoán vị nhiều hơn một lần

Tổ hợp là tập hợp các phần tử của một tập hợp. Chính thức hơn, một k-tổ hợp là một tập hợp con của k phần tử từ một tập hợp. Không giống như hoán vị, các kết hợp không có thứ tự. Ví dụ: 2 tổ hợp của tập hợp {A, B, C} là {A, B}, {A, C} và {B, C}. Tổ hợp 3 của tập hợp {A, B, C} là {A, B, C}

Số hạng n chọn k dùng để chỉ số các tổ hợp có thể (không lặp lại) của k phần tử có thể được chọn từ một tập hợp n phần tử. (Một số nhà toán học sử dụng thuật ngữ n chọn r. ) Khái niệm này không liên quan gì đến bản thân các phần tử, chỉ là số lượng của chúng. Ví dụ: 4 chọn 2 là 6, vì có 6 cách chọn 2 phần tử trong tập hợp 4 phần tử như {A, B, C, D}. {A, B}, {A, C}, {A, D}, {B, C}, {B, D} và {C, D}. Trong khi đó, 3 chọn 3 là 1, vì chỉ có một tổ hợp 3 từ bộ ba phần tử như {A, B, C}; . Công thức tính n chọn k là (n. ) / (k. × (n – k). ). Nhớ lại rằng n. là ký hiệu cho giai thừa. 5. là 5 × 4 × 3 × 2 × 1

Thuật ngữ n multichoose k đề cập đến số lượng kết hợp có thể có với sự lặp lại của k phần tử có thể được chọn từ một tập hợp gồm n phần tử. Bởi vì tổ hợp k là tập hợp và tập hợp không có phần tử trùng lặp, tổ hợp k không có sự lặp lại. Khi chúng tôi sử dụng kết hợp k với các phần tử trùng lặp, chúng tôi đặc biệt gọi chúng là kết hợp k với sự lặp lại

Hãy nhớ rằng, cả khi có lặp lại và không lặp lại, bạn có thể coi hoán vị là một cách sắp xếp nhất định của tất cả các phần tử trong một tập hợp, trong khi tổ hợp là một lựa chọn không có thứ tự của các phần tử nhất định từ một tập hợp. Các hoán vị có thứ tự và sử dụng tất cả các phần tử từ một tập hợp, trong khi các kết hợp không có thứ tự và sử dụng bất kỳ số lượng phần tử nào từ một tập hợp. Để hiểu rõ hơn về các thuật ngữ này, hãy chỉ ra sự khác biệt giữa hoán vị và tổ hợp, có lặp lại và không lặp lại, của tập hợp {A, B, C}

Bảng 6-1. Tất cả các Hoán vị và Tổ hợp có thể có, có và không có Lặp lại, của Tập hợp {A, B, C}

Hoán vịKết hợpKhông lặp lạiABC, ACB, BAC, BCA, CAB(Không), A, B, C, AB, AC, BC, ABCCó lặp lạiAAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC

Thật đáng ngạc nhiên khi số lượng các hoán vị và tổ hợp tăng lên nhanh như thế nào khi chúng ta thêm các phần tử vào một tập hợp. Vụ nổ tổ hợp này được nắm bắt bởi các công thức trong. Ví dụ: một tập hợp gồm 10 phần tử thì có 10. , hoặc 3.628.800, các hoán vị có thể có, nhưng một tập hợp có số phần tử gấp đôi có 20. , hoặc 2.432.902.008.176.640.000, hoán vị

Bảng 6-2. Tính số các hoán vị và tổ hợp có thể có, có lặp lại và không lặp lại, của một tập hợp gồm n phần tử

Hoán vị Tổ hợp Không lặp lại. 2nVới sự lặp lạinn2n chọn n, hoặc
(2n). / (N. )2

Lưu ý rằng các hoán vị không lặp lại luôn có cùng kích thước với tập hợp. Ví dụ: các hoán vị của {A, B, C} luôn dài ba chữ cái. ABC, ACB, BAC, v.v. Tuy nhiên, hoán vị với sự lặp lại có thể có độ dài bất kỳ. hiển thị các hoán vị ba chữ cái của {A, B, C} từ AAA đến CCC, nhưng bạn cũng có thể, chẳng hạn, có các hoán vị năm chữ cái với sự lặp lại từ AAAAA đến CCCCC. Số các hoán vị lặp n phần tử dài k phần tử là nk. liệt kê nó là nn cho các hoán vị với sự lặp lại cũng dài n phần tử

Thứ tự quan trọng đối với hoán vị, nhưng không phải đối với kết hợp. Trong khi AAB, ABA và BAA được coi là cùng một tổ hợp với sự lặp lại, chúng được coi là ba hoán vị riêng biệt với sự lặp lại

Tìm tất cả các hoán vị mà không cần lặp lại. Biểu đồ chỗ ngồi trong đám cưới

Hãy tưởng tượng bạn phải sắp xếp sơ đồ chỗ ngồi cho một tiệc cưới với những yêu cầu xã giao tế nhị. Một số khách ghét nhau, trong khi những người khác yêu cầu ngồi gần một vị khách có ảnh hưởng. Các ghế ở bàn hình chữ nhật tạo thành một hàng dài và thẳng chứ không phải hình tròn. Sẽ rất hữu ích cho việc lập kế hoạch của bạn khi xem mọi thứ tự có thể có của khách—nghĩa là mọi hoán vị mà không lặp lại nhóm khách. Không xảy ra sự lặp lại vì mỗi khách chỉ xuất hiện trong sơ đồ chỗ ngồi một lần

Hãy sử dụng một ví dụ đơn giản về Alice, Bob và Carol hoặc {A, B, C}. hiển thị tất cả sáu hoán vị có thể có của ba khách dự tiệc cưới này

Một cách chúng ta có thể xác định số lượng hoán vị mà không cần lặp lại là sử dụng chiến lược đệ quy đầu đuôi. Chúng tôi chọn một phần tử từ tập hợp làm phần tử đầu. Sau đó, chúng tôi nhận được mọi hoán vị của các phần tử còn lại (tạo thành đuôi) và với mỗi hoán vị, chúng tôi đặt phần đầu vào mọi vị trí có thể trong hoán vị

Trong ví dụ ABC của chúng tôi, chúng tôi sẽ bắt đầu với Alice (A) là đầu và Bob và Carol (BC) là đuôi. Các hoán vị của {B, C} là BC và CB. (Làm thế nào chúng tôi có BC và CB được giải thích trong đoạn tiếp theo, vì vậy bây giờ hãy đặt câu hỏi đó sang một bên. ) Chúng tôi sẽ đặt A ở mọi vị trí có thể có trong BC. Nghĩa là, chúng ta đặt Alice trước Bob (ABC), ở giữa Bob và Carol (BAC) và sau Carol (BCA). Điều này tạo ra các hoán vị ABC, BAC và BCA. Chúng tôi cũng đặt A vào mọi vị trí có thể có trong CB, tạo ra ACB, CAB và CBA. Điều này tạo ra tất cả sáu hoán vị của Alice, Bob và Carol đang ngồi ở bàn tiếp tân. Bây giờ chúng ta có thể chọn cách sắp xếp dẫn đến ít đánh nhau nhất (hoặc nhiều đánh nhau nhất, nếu bạn muốn có một tiệc cưới đáng nhớ)

Hình 6-2. Tất cả sáu hoán vị có thể có của ba khách dự tiệc cưới tại một bàn

Tất nhiên, để có được mọi hoán vị của {B, C}, chúng tôi sẽ lặp lại quy trình một cách đệ quy với B là đầu và C là đuôi. Hoán vị của một ký tự đơn là chính ký tự đó; . Bằng cách đặt đầu B vào mọi vị trí có thể có trong C, chúng ta có được các hoán vị BC và CB mà chúng ta đã sử dụng trong đoạn trước. Hãy nhớ rằng, mặc dù thứ tự không quan trọng với các tập hợp (vì {B, C} giống với {C, B}), nhưng nó lại quan trọng với các hoán vị (BC không phải là bản sao của CB)

Hàm hoán vị đệ quy của chúng tôi chấp nhận làm đối số là một chuỗi ký tự và trả về một mảng các chuỗi của mọi hoán vị có thể có của các ký tự đó. Hãy hỏi ba câu hỏi về thuật toán đệ quy của chúng tôi cho chức năng này

Trường hợp cơ bản là gì?
Đối số nào được truyền cho lệnh gọi hàm đệ quy? . Một cuộc gọi đệ quy riêng biệt được thực hiện cho mỗi ký tự bị thiếu
Làm thế nào để lập luận này trở nên gần gũi hơn với trường hợp cơ sở?

Thuật toán hoán vị đệ quy được thực hiện trong hoán vị. py

def getPerms(chars, indent=0):
    print('.' * indent + 'Start of getPerms("' + chars + '")')
    if len(chars) == 1: ❶
        # BASE CASE
        print('.' * indent + 'When chars = "' + chars + '" base case returns', chars)
        return [chars]

    # RECURSIVE CASE
    permutations = []
    head = chars[0] ❷
    tail = chars[1:]
    tailPermutations = getPerms(tail, indent + 1)
    for tailPerm in tailPermutations: ❸
        print('.' * indent + 'When chars =', chars, 'putting head', head, 'in all places in', tailPerm)
        for i in range(len(tailPerm) + 1): ❹
            newPerm = tailPerm[0:i] + head + tailPerm[i:]
            print('.' * indent + 'New permutation:', newPerm)
            permutations.append(newPerm)
    print('.' * indent + 'When chars =', chars, 'results are', permutations)
    return permutations

print('Permutations of "ABCD":')
print('Results:', ','.join(getPerms('ABCD')))

Chương trình JavaScript tương đương ở dạng hoán vị. html

Đầu ra của các chương trình này là như sau

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

Khi

9 được gọi, đầu tiên nó sẽ kiểm tra trường hợp cơ sở ❶. Nếu chuỗi

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 chỉ dài một ký tự, nó chỉ có thể có một hoán vị. chính chuỗi

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0. Hàm trả về chuỗi này trong một mảng

Mặt khác, trong trường hợp đệ quy, hàm sẽ tách ký tự đầu tiên của đối số

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 thành biến

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

3 và phần còn lại thành biến

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

4 ❷. Hàm thực hiện cuộc gọi đệ quy tới

9 để lấy tất cả các hoán vị của chuỗi trong

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

4. Vòng lặp

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

7 đầu tiên ❸ lặp qua từng hoán vị này và vòng lặp

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

7 thứ hai ❹ tạo ra một hoán vị mới bằng cách đặt ký tự

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

3 ở mọi vị trí có thể trong chuỗi

Ví dụ: nếu

9 được gọi với

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

1 cho đối số

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0, thì

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

3 là

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

4 và

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

4 là

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

6. Cuộc gọi

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

7 trả về một mảng các hoán vị đuôi,

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

8. Vòng lặp

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

7 đầu tiên bắt đầu với hoán vị

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

6 và vòng lặp

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

7 thứ hai đặt chuỗi

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

4 vào ____12_______3 ở mỗi vị trí có thể, tạo ra

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

1,

5,

6,

7. Điều này được lặp lại với các hoán vị đuôi còn lại và toàn bộ danh sách sau đó được trả về bởi hàm

9

Nhận hoán vị với các vòng lặp lồng nhau. Một cách tiếp cận kém lý tưởng

Giả sử chúng ta có một khóa xe đạp đơn giản, như trong , với tổ hợp bốn chữ số. Tổ hợp này có 10.000 hoán vị có thể có của các chữ số (0000 đến 9999), nhưng chỉ có một sẽ mở khóa. (Chúng được gọi là khóa kết hợp; tuy nhiên, trong ngữ cảnh này, sẽ chính xác hơn nếu gọi chúng là hoán vị với khóa lặp lại, vì thứ tự quan trọng. )

Bây giờ, giả sử chúng ta có một ổ khóa đơn giản hơn nhiều chỉ với năm chữ cái từ A đến E. Chúng tôi có thể tính toán số lượng kết hợp có thể là 54 hoặc 5 × 5 × 5 × 5 hoặc 625. Một khóa kết hợp gồm k ký tự, mỗi ký tự được chọn từ một tập hợp n khả năng, là nk. Nhưng để có được một danh sách các kết hợp có liên quan nhiều hơn một chút

Hình 6-3. Khóa xe đạp kết hợp bốn chữ số có 104 hoặc 10.000 hoán vị có thể có với sự lặp lại (ảnh do Shaun Fisher cung cấp, CC BY 2. 0 giấy phép)

Một cách để có được hoán vị với sự lặp lại là với các vòng lặp lồng nhau—tức là, một vòng lặp bên trong một vòng lặp khác. Vòng lặp bên trong đi qua mọi phần tử trong một tập hợp, trong khi vòng lặp bên ngoài thực hiện tương tự trong khi lặp lại vòng lặp bên trong. Tạo tất cả các hoán vị k ký tự có thể, mỗi ký tự được chọn từ một bộ n khả năng, yêu cầu k vòng lặp lồng nhau

Ví dụ, lồng nhauLoopPermutations. py chứa mã tạo tất cả 3 tổ hợp {A, B, C, D, E}

con trăn

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

Và lồng nhauLoopPermutations. html chứa chương trình JavaScript tương đương

JavaScript

Đầu ra của các chương trình này trông như thế này

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

Vấn đề với việc tạo hoán vị với bốn vòng lặp lồng nhau là nó chỉ hoạt động đối với các hoán vị có chính xác bốn ký tự. Các vòng lồng nhau không thể tạo hoán vị cho độ dài tùy ý. Thay vào đó, chúng ta có thể sử dụng hàm đệ quy, như được mô tả trong phần tiếp theo

Bạn có thể nhớ sự khác biệt giữa các hoán vị có lặp lại và không lặp lại với các ví dụ trong chương này. Các hoán vị không lặp lại đi qua tất cả các thứ tự có thể có của các phần tử trong một tập hợp, như ví dụ về sơ đồ chỗ ngồi cho khách dự đám cưới của chúng tôi. Các hoán vị có lặp lại đi qua tất cả các tổ hợp có thể có của khóa tổ hợp;

Hoán vị với sự lặp lại. Trình bẻ khóa mật khẩu

Hãy tưởng tượng bạn đã nhận được một tệp mã hóa nhạy cảm từ một nhà báo vừa qua đời. Trong tin nhắn cuối cùng của họ, nhà báo nói với bạn rằng hồ sơ chứa các hồ sơ trốn thuế của một tỷ phú bất chính. Họ không có mật khẩu để giải mã tệp, nhưng họ biết rằng nó dài đúng bốn ký tự; . Những ký tự này có thể xuất hiện nhiều lần. Ví dụ: các mật khẩu có thể là JPB2, JJJJ và 2442

Để tạo danh sách tất cả các mật khẩu gồm bốn ký tự có thể dựa trên thông tin này, bạn muốn có được tất cả các hoán vị bốn phần tử có thể có với sự lặp lại của tập hợp {J, P, B, 2, 4, 8}. Mỗi trong số bốn ký tự trong mật khẩu có thể là một trong sáu ký tự có thể, tạo ra các hoán vị có thể là 6 × 6 × 6 × 6 hoặc 64 hoặc 1.296. Chúng tôi muốn tạo các hoán vị của {J, P, B, 2, 4, 8} chứ không phải các kết hợp, bởi vì thứ tự quan trọng;

Hãy hỏi ba câu hỏi về thuật toán đệ quy về hàm hoán vị của chúng ta. Thay vì k, chúng tôi sẽ sử dụng tên mô tả hơn

9

Trường hợp cơ bản là gì?

Đối số nào được truyền cho lệnh gọi hàm đệ quy? . Các cuộc gọi đệ quy giảm đối số

9 trong khi nối thêm một ký tự từ

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 vào đối số

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

2

Làm thế nào để lập luận này trở nên gần gũi hơn với trường hợp cơ sở?

Thuật toán hoán vị đệ quy có lặp lại được triển khai trong permutationsWithRepetition. py

def getPermsWithRep(chars, permLength=None, prefix=''):
    indent = '.' * len(prefix)
    print(indent + 'Start, args=("' + chars + '", ' + str(permLength) + ', "' + prefix + '")')
    if permLength is None:
        permLength = len(chars)

    # BASE CASE
    if (permLength == 0): ❶
        print(indent + 'Base case reached, returning', [prefix])
        return [prefix]

    # RECURSIVE CASE
    # Create a new prefix by adding each character to the current prefix.
    results = []
    print(indent + 'Adding each char to prefix "' + prefix + '".')
    for char in chars:
        newPrefix = prefix + char ❷

        # Decrease permLength by one because we added one character to the prefix.
        results.extend(getPermsWithRep (chars, permLength - 1, newPrefix)) ❸
    print(indent + 'Returning', results)
    return results


print('All permutations with repetition of JPB123:')
print(getPermsWithRep('JPB123', 4))

Chương trình JavaScript tương đương ở dạng hoán vịWithRepetition. html

Đầu ra của các chương trình này được hiển thị ở đây

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

Hàm

def getPermsWithRep(chars, permLength=None, prefix=''):
    indent = '.' * len(prefix)
    print(indent + 'Start, args=("' + chars + '", ' + str(permLength) + ', "' + prefix + '")')
    if permLength is None:
        permLength = len(chars)

    # BASE CASE
    if (permLength == 0): ❶
        print(indent + 'Base case reached, returning', [prefix])
        return [prefix]

    # RECURSIVE CASE
    # Create a new prefix by adding each character to the current prefix.
    results = []
    print(indent + 'Adding each char to prefix "' + prefix + '".')
    for char in chars:
        newPrefix = prefix + char ❷

        # Decrease permLength by one because we added one character to the prefix.
        results.extend(getPermsWithRep (chars, permLength - 1, newPrefix)) ❸
    print(indent + 'Returning', results)
    return results


print('All permutations with repetition of JPB123:')
print(getPermsWithRep('JPB123', 4))

3 có đối số chuỗi

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

2 bắt đầu dưới dạng chuỗi trống theo mặc định. Khi hàm được gọi, đầu tiên hàm sẽ kiểm tra trường hợp cơ sở ❶. Nếu

9, độ dài của các hoán vị, là

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

1, thì một mảng có

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

2 được trả về

Mặt khác, trong trường hợp đệ quy, đối với mỗi ký tự trong đối số

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0, hàm tạo một tiền tố mới ❷ để chuyển đến lệnh gọi đệ quy

def getPermsWithRep(chars, permLength=None, prefix=''):
    indent = '.' * len(prefix)
    print(indent + 'Start, args=("' + chars + '", ' + str(permLength) + ', "' + prefix + '")')
    if permLength is None:
        permLength = len(chars)

    # BASE CASE
    if (permLength == 0): ❶
        print(indent + 'Base case reached, returning', [prefix])
        return [prefix]

    # RECURSIVE CASE
    # Create a new prefix by adding each character to the current prefix.
    results = []
    print(indent + 'Adding each char to prefix "' + prefix + '".')
    for char in chars:
        newPrefix = prefix + char ❷

        # Decrease permLength by one because we added one character to the prefix.
        results.extend(getPermsWithRep (chars, permLength - 1, newPrefix)) ❸
    print(indent + 'Returning', results)
    return results


print('All permutations with repetition of JPB123:')
print(getPermsWithRep('JPB123', 4))

3. Cuộc gọi đệ quy này vượt qua

0 cho đối số

9

Đối số

9 bắt đầu ở độ dài của các hoán vị và giảm đi một đối với mỗi lệnh gọi đệ quy ❸. Và đối số

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

2 bắt đầu dưới dạng chuỗi trống và tăng thêm một ký tự cho mỗi lệnh gọi đệ quy. Vì vậy, vào thời điểm trường hợp cơ sở của

4 đạt được, chuỗi

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

2 có độ dài hoán vị đầy đủ là

6

Ví dụ, hãy xem xét trường hợp gọi

7. Đối số

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

2 mặc định là chuỗi trống. Hàm thực hiện một cuộc gọi đệ quy với mỗi ký tự của

9 được nối với chuỗi tiền tố trống làm tiền tố mới. Gọi

7 thực hiện ba cuộc gọi đệ quy này

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

1

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

2

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

3

Mỗi cuộc gọi trong số ba cuộc gọi này sẽ thực hiện ba cuộc gọi đệ quy của riêng mình, nhưng sẽ vượt qua

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

1 cho

9 thay vì

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

6. Trường hợp cơ sở xảy ra khi

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

7, vì vậy những trường hợp này trả về tiền tố của chúng. Đây là cách tất cả chín hoán vị được tạo ra. Hàm

def getPermsWithRep(chars, permLength=None, prefix=''):
    indent = '.' * len(prefix)
    print(indent + 'Start, args=("' + chars + '", ' + str(permLength) + ', "' + prefix + '")')
    if permLength is None:
        permLength = len(chars)

    # BASE CASE
    if (permLength == 0): ❶
        print(indent + 'Base case reached, returning', [prefix])
        return [prefix]

    # RECURSIVE CASE
    # Create a new prefix by adding each character to the current prefix.
    results = []
    print(indent + 'Adding each char to prefix "' + prefix + '".')
    for char in chars:
        newPrefix = prefix + char ❷

        # Decrease permLength by one because we added one character to the prefix.
        results.extend(getPermsWithRep (chars, permLength - 1, newPrefix)) ❸
    print(indent + 'Returning', results)
    return results


print('All permutations with repetition of JPB123:')
print(getPermsWithRep('JPB123', 4))

3 tạo hoán vị của các tập hợp lớn hơn theo cùng một cách

Nhận kết hợp K với đệ quy

Nhớ lại rằng thứ tự không có ý nghĩa đối với các kết hợp theo cách đối với hoán vị. Tuy nhiên, việc tạo tất cả k-kết hợp của một tập hợp hơi phức tạp vì bạn không muốn thuật toán của mình tạo ra các bản sao. nếu bạn tạo tổ hợp 2 tổ hợp AB từ tập {A, B, C}, bạn không muốn tạo cả BA, vì nó là tổ hợp 2 tổ hợp giống như AB

Để tìm hiểu cách chúng ta có thể viết mã đệ quy để giải quyết vấn đề này, hãy xem cách một cây có thể mô tả trực quan việc tạo ra tất cả k-tổ hợp của một tập hợp. hiển thị một cây với tất cả các kết hợp từ tập hợp {A, B, C, D}

Hình 6-4. Cây hiển thị mọi tổ hợp k có thể có (từ 0 đến 4) từ tập hợp {A, B, C, D}

Ví dụ, để thu thập 3 tổ hợp từ cây này, hãy bắt đầu từ nút gốc ở trên cùng và thực hiện duyệt cây theo chiều sâu đến cấp độ 3 tổ hợp, đồng thời ghi nhớ từng chữ cái của nút trên đường đến cuối. (Tìm kiếm theo chiều sâu được thảo luận trong Chương 4. ) Tổ hợp 3 đầu tiên của chúng tôi sẽ đi từ gốc đến A ở cấp độ kết hợp 1, sau đó xuống B ở cấp độ kết hợp 2, sau đó đến C ở cấp độ kết hợp 3, nơi chúng tôi dừng lại với 3- kết hợp hoàn chỉnh của mình . ABC. Đối với tổ hợp tiếp theo, chúng ta đi từ gốc đến A đến B đến D, cho chúng ta tổ hợp ABD. Chúng tôi tiếp tục làm điều này cho ACD và BCD. Cây của chúng tôi có bốn nút ở cấp độ 3 kết hợp và bốn kết hợp 3 từ {A, B, C, D}. ABC, ABD, ACD và BCD

Lưu ý rằng chúng tôi tạo cây bằng cách bắt đầu bằng một chuỗi trống cho nút gốc. Đây là mức kết hợp 0 và nó áp dụng cho tất cả các kết hợp của các lựa chọn không từ tập hợp; . Các nút con của gốc là tất cả các phần tử từ tập hợp. Trong trường hợp của chúng tôi, đó là tất cả bốn yếu tố từ {A, B, C, D}. Mặc dù các tập hợp không có thứ tự, nhưng chúng ta cần nhất quán trong việc sử dụng thứ tự ABCD của tập hợp trong khi tạo cây này. Điều này là do con của mỗi nút bao gồm các chữ cái sau nó trong chuỗi ABCD. tất cả các nút A có con B, C và D;

Mặc dù nó không liên quan trực tiếp đến hàm kết hợp đệ quy, nhưng cũng lưu ý mẫu về số lượng kết hợp k ở mỗi cấp độ

Các mức kết hợp 0 và 4 kết hợp đều có một kết hợp. chuỗi rỗng và ABCD, tương ứng
Cả cấp độ kết hợp 1 và kết hợp 3 đều có bốn kết hợp. A, B, C, D lần lượt là ABC, ABD, ACD, BCD
Cấp độ kết hợp 2 ở giữa có nhiều kết hợp nhất ở mức sáu. AB, AC, AD, BC, BD và CD

Lý do số lượng kết hợp tăng lên, đạt cực đại ở giữa và sau đó giảm xuống là k kết hợp là gương của nhau. Ví dụ: tổ hợp 1 được tạo từ các phần tử không được chọn cho tổ hợp 3

1 tổ hợp A là gương của 3 tổ hợp BCD
1 tổ hợp B là gương của 3 tổ hợp ACD
1 tổ hợp C là gương của 3 tổ hợp ABD
1 tổ hợp D là gương của 3 tổ hợp ABC

Chúng ta sẽ tạo một hàm tên là

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

9 nhận hai đối số. một chuỗi

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 với các chữ cái để lấy các kết hợp từ đó và kích thước của các kết hợp

6. Giá trị trả về là một mảng các chuỗi kết hợp từ chuỗi

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0, mỗi chuỗi có độ dài

6

Chúng ta sẽ sử dụng kỹ thuật head-tail với đối số

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0. Ví dụ: giả sử chúng ta gọi

def getCombos(chars, k, indent=0):
    debugMsg = '.' * indent + "In getCombos('" + chars + "', " + str(k) + ")"
    print(debugMsg + ', start.')
    if k == 0:
        # BASE CASE
        print(debugMsg + " base case returns ['']")
        # If k asks for 0-combinations, return '' as the selection of
        # zero letters from chars.
        return ['']
    elif chars == '':
        # BASE CASE
        print(debugMsg + ' base case returns []')
        return [] # A blank chars has no combinations, no matter what k is.

    # RECURSIVE CASE
    combinations = []
  ❶ # First part, get the combos that include the head:
    head = chars[:1]
    tail = chars[1:]
    print(debugMsg + " part 1, get combos with head '" + head + "'")
  ❷ tailCombos = getCombos(tail, k - 1, indent + 1)
    print('.' * indent + "Adding head '" + head + "' to tail combos:")
    for tailCombo in tailCombos:
        print('.' * indent + 'New combination', head + tailCombo)
        combinations.append(head + tailCombo)

  ❸ # Second part, get the combos that don't include the head:
    print(debugMsg + " part 2, get combos without head '" + head + "')")
  ❹ combinations.extend(getCombos(tail, k, indent + 1))

    print(debugMsg + ' results are', combinations)
    return combinations

print('2-combinations of "ABC":')
print('Results:', getCombos('ABC', 2))

5 để lấy tất cả 2 tổ hợp từ {A, B, C}. Hàm sẽ đặt

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

4 làm đầu và

def getCombos(chars, k, indent=0):
    debugMsg = '.' * indent + "In getCombos('" + chars + "', " + str(k) + ")"
    print(debugMsg + ', start.')
    if k == 0:
        # BASE CASE
        print(debugMsg + " base case returns ['']")
        # If k asks for 0-combinations, return '' as the selection of
        # zero letters from chars.
        return ['']
    elif chars == '':
        # BASE CASE
        print(debugMsg + ' base case returns []')
        return [] # A blank chars has no combinations, no matter what k is.

    # RECURSIVE CASE
    combinations = []
  ❶ # First part, get the combos that include the head:
    head = chars[:1]
    tail = chars[1:]
    print(debugMsg + " part 1, get combos with head '" + head + "'")
  ❷ tailCombos = getCombos(tail, k - 1, indent + 1)
    print('.' * indent + "Adding head '" + head + "' to tail combos:")
    for tailCombo in tailCombos:
        print('.' * indent + 'New combination', head + tailCombo)
        combinations.append(head + tailCombo)

  ❸ # Second part, get the combos that don't include the head:
    print(debugMsg + " part 2, get combos without head '" + head + "')")
  ❹ combinations.extend(getCombos(tail, k, indent + 1))

    print(debugMsg + ' results are', combinations)
    return combinations

print('2-combinations of "ABC":')
print('Results:', getCombos('ABC', 2))

7 làm đuôi. hiển thị cây để chọn 2 kết hợp từ {A, B, C}

Hình 6-5. Cây hiển thị mọi tổ hợp 2 có thể có từ tập hợp {A, B, C}

Hãy hỏi ba câu hỏi thuật toán đệ quy của chúng tôi

Trường hợp cơ sở là gì? . Trường hợp thứ hai xảy ra nếu

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 là chuỗi trống, là một mảng trống vì không thể thực hiện kết hợp nào từ một chuỗi trống

Đối số nào được truyền cho lệnh gọi hàm đệ quy? . Đối với cuộc gọi đệ quy thứ hai, đuôi của

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 và

6 được thông qua

Làm thế nào để lập luận này trở nên gần gũi hơn với trường hợp cơ sở?

Mã Python để tạo các kết hợp nằm trong các kết hợp. py

con trăn

def getCombos(chars, k, indent=0):
    debugMsg = '.' * indent + "In getCombos('" + chars + "', " + str(k) + ")"
    print(debugMsg + ', start.')
    if k == 0:
        # BASE CASE
        print(debugMsg + " base case returns ['']")
        # If k asks for 0-combinations, return '' as the selection of
        # zero letters from chars.
        return ['']
    elif chars == '':
        # BASE CASE
        print(debugMsg + ' base case returns []')
        return [] # A blank chars has no combinations, no matter what k is.

    # RECURSIVE CASE
    combinations = []
  ❶ # First part, get the combos that include the head:
    head = chars[:1]
    tail = chars[1:]
    print(debugMsg + " part 1, get combos with head '" + head + "'")
  ❷ tailCombos = getCombos(tail, k - 1, indent + 1)
    print('.' * indent + "Adding head '" + head + "' to tail combos:")
    for tailCombo in tailCombos:
        print('.' * indent + 'New combination', head + tailCombo)
        combinations.append(head + tailCombo)

  ❸ # Second part, get the combos that don't include the head:
    print(debugMsg + " part 2, get combos without head '" + head + "')")
  ❹ combinations.extend(getCombos(tail, k, indent + 1))

    print(debugMsg + ' results are', combinations)
    return combinations

print('2-combinations of "ABC":')
print('Results:', getCombos('ABC', 2))

Chương trình JavaScript tương đương ở dạng kết hợp. html

Đầu ra của các chương trình này là như sau

1

Mỗi lệnh gọi hàm

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

9 có hai lệnh gọi đệ quy cho hai phần của thuật toán. Đối với ví dụ về

def getCombos(chars, k, indent=0):
    debugMsg = '.' * indent + "In getCombos('" + chars + "', " + str(k) + ")"
    print(debugMsg + ', start.')
    if k == 0:
        # BASE CASE
        print(debugMsg + " base case returns ['']")
        # If k asks for 0-combinations, return '' as the selection of
        # zero letters from chars.
        return ['']
    elif chars == '':
        # BASE CASE
        print(debugMsg + ' base case returns []')
        return [] # A blank chars has no combinations, no matter what k is.

    # RECURSIVE CASE
    combinations = []
  ❶ # First part, get the combos that include the head:
    head = chars[:1]
    tail = chars[1:]
    print(debugMsg + " part 1, get combos with head '" + head + "'")
  ❷ tailCombos = getCombos(tail, k - 1, indent + 1)
    print('.' * indent + "Adding head '" + head + "' to tail combos:")
    for tailCombo in tailCombos:
        print('.' * indent + 'New combination', head + tailCombo)
        combinations.append(head + tailCombo)

  ❸ # Second part, get the combos that don't include the head:
    print(debugMsg + " part 2, get combos without head '" + head + "')")
  ❹ combinations.extend(getCombos(tail, k, indent + 1))

    print(debugMsg + ' results are', combinations)
    return combinations

print('2-combinations of "ABC":')
print('Results:', getCombos('ABC', 2))

5 của chúng tôi, phần đầu tiên ❶ là lấy tất cả các kết hợp bao gồm phần đầu

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

4. Trong cây, điều này tạo ra tất cả các kết hợp bên dưới nút A ở mức 1 kết hợp

Chúng ta có thể làm điều này bằng cách chuyển phần đuôi và

03 cho lệnh gọi hàm đệ quy đầu tiên.

15 ❷. Chúng tôi thêm

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

4 vào mỗi kết hợp mà lệnh gọi hàm đệ quy này trả về. Hãy sử dụng nguyên tắc nhảy vọt của niềm tin và chỉ cần giả sử rằng

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

9 của chúng ta trả về đúng một danh sách k-kết hợp,

18, mặc dù chúng ta chưa viết xong nó. Bây giờ chúng tôi có tất cả k-kết hợp bao gồm đầu

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

4 trong một mảng để giữ kết quả của chúng tôi.

20

Phần thứ hai ❸ có tất cả các kết hợp không bao gồm phần đầu

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

4. Trong cây, điều này tạo ra tất cả các kết hợp ở bên phải của nút A ở cấp độ kết hợp 1. Chúng ta có thể làm điều này bằng cách chuyển đuôi và

6 đến lệnh gọi hàm đệ quy thứ hai.

23. Điều này trả về

24, vì BC là tổ hợp 2 duy nhất của BC

Kết quả từ hai lệnh gọi đệ quy của

def getCombos(chars, k, indent=0):
    debugMsg = '.' * indent + "In getCombos('" + chars + "', " + str(k) + ")"
    print(debugMsg + ', start.')
    if k == 0:
        # BASE CASE
        print(debugMsg + " base case returns ['']")
        # If k asks for 0-combinations, return '' as the selection of
        # zero letters from chars.
        return ['']
    elif chars == '':
        # BASE CASE
        print(debugMsg + ' base case returns []')
        return [] # A blank chars has no combinations, no matter what k is.

    # RECURSIVE CASE
    combinations = []
  ❶ # First part, get the combos that include the head:
    head = chars[:1]
    tail = chars[1:]
    print(debugMsg + " part 1, get combos with head '" + head + "'")
  ❷ tailCombos = getCombos(tail, k - 1, indent + 1)
    print('.' * indent + "Adding head '" + head + "' to tail combos:")
    for tailCombo in tailCombos:
        print('.' * indent + 'New combination', head + tailCombo)
        combinations.append(head + tailCombo)

  ❸ # Second part, get the combos that don't include the head:
    print(debugMsg + " part 2, get combos without head '" + head + "')")
  ❹ combinations.extend(getCombos(tail, k, indent + 1))

    print(debugMsg + ' results are', combinations)
    return combinations

print('2-combinations of "ABC":')
print('Results:', getCombos('ABC', 2))

5,

20 và

24, được nối với nhau và trả về.

28 ❹. Hàm

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

9 tạo kết hợp các tập hợp lớn hơn theo cùng một cách

Nhận tất cả các kết hợp của dấu ngoặc đơn cân bằng

Một chuỗi có dấu ngoặc đơn cân bằng nếu mỗi dấu ngoặc đơn mở được theo sau bởi chính xác một dấu ngoặc đơn đóng. Ví dụ:

30 và

31 là các chuỗi có hai cặp dấu ngoặc đơn cân bằng, nhưng

32 và

33 không cân bằng. Các chuỗi này còn được gọi là các từ Dyck, theo tên nhà toán học Walther von Dyck

Một câu hỏi phỏng vấn mã hóa phổ biến là viết một hàm đệ quy, với số lượng cặp dấu ngoặc đơn cho trước, tạo ra tất cả các kết hợp có thể có của các dấu ngoặc đơn cân bằng. Ví dụ: một cuộc gọi

34 sẽ trả về

35. Lưu ý rằng việc gọi

36n

37 trả về các chuỗi có độ dài 2n ký tự, vì mỗi chuỗi bao gồm n cặp dấu ngoặc đơn

Chúng ta có thể cố gắng giải quyết vấn đề này bằng cách tìm tất cả các hoán vị của các cặp ký tự trong dấu ngoặc đơn, nhưng điều đó sẽ dẫn đến cả chuỗi dấu ngoặc đơn cân bằng và không cân bằng. Ngay cả khi chúng tôi lọc ra các chuỗi không hợp lệ sau này, 2n. hoán vị tồn tại cho n cặp dấu ngoặc đơn. Thuật toán đó quá chậm để trở thành hiện thực

Thay vào đó, chúng ta có thể thực hiện một hàm đệ quy để tạo ra tất cả các chuỗi dấu ngoặc đơn cân đối. Hàm

38 của chúng tôi lấy một số nguyên của số cặp dấu ngoặc đơn và trả về danh sách các chuỗi dấu ngoặc đơn cân đối. Hàm xây dựng các chuỗi này bằng cách thêm dấu ngoặc đơn mở hoặc đóng. Chỉ có thể thêm dấu ngoặc đơn mở nếu dấu ngoặc đơn mở vẫn được sử dụng. Chỉ có thể thêm dấu ngoặc đơn đóng nếu nhiều dấu ngoặc đơn mở hơn đã được thêm vào so với dấu ngoặc đơn đóng cho đến nay

Chúng tôi sẽ theo dõi số lượng dấu ngoặc đơn mở và đóng còn lại được sử dụng với các tham số chức năng có tên là

39 và

40. Chuỗi hiện đang được tạo là một tham số chức năng khác có tên là

41, phục vụ mục đích tương tự như tham số

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

2 trong chương trình hoán vịWithRepetition. Trường hợp cơ sở đầu tiên xảy ra khi

39 và

40 đều là

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

1 và không còn dấu ngoặc đơn nào để thêm vào chuỗi

41. Trường hợp cơ sở thứ hai xảy ra sau khi hai trường hợp đệ quy đã nhận được danh sách các chuỗi dấu ngoặc đơn cân bằng sau khi thêm dấu ngoặc đơn mở và/hoặc đóng (nếu có thể)

Hãy hỏi ba câu hỏi thuật toán đệ quy về hàm

38

Trường hợp cơ bản là gì? . Trường hợp cơ sở thứ hai luôn xảy ra sau khi trường hợp đệ quy kết thúc
Đối số nào được truyền cho lệnh gọi hàm đệ quy?
Làm thế nào để lập luận này trở nên gần gũi hơn với trường hợp cơ sở?

Dấu ngoặc đơn cân bằng. tệp py chứa mã Python cho hàm đệ quy dấu ngoặc đơn cân bằng của chúng tôi

2

Dấu ngoặc đơn cân bằng. tệp html chứa JavaScript tương đương với chương trình này

Đầu ra của các chương trình này trông như thế này

4

Hàm

38 ❶ yêu cầu một đối số, số cặp dấu ngoặc đơn, khi được người dùng gọi. Tuy nhiên, nó cần chuyển thông tin bổ sung trong các đối số cho các lệnh gọi đệ quy của nó. Chúng bao gồm số lượng dấu ngoặc đơn mở vẫn được thêm vào (

39), số lượng dấu ngoặc đơn đóng vẫn được thêm vào (

40) và chuỗi dấu ngoặc đơn cân bằng hiện tại đang được tạo (

41). Cả

39 và

40 đều bắt đầu bằng cùng một giá trị với đối số

49 và

41 bắt đầu bằng chuỗi trống. Đối số

8 chỉ được sử dụng cho đầu ra gỡ lỗi để hiển thị mức gọi hàm đệ quy của chương trình

Đầu tiên, hàm kiểm tra số lượng dấu ngoặc đơn mở và đóng còn lại để thêm vào ❷. Nếu cả hai đều là

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
--snip--
E E E C
E E E D
E E E E

1, chúng tôi đã đạt đến trường hợp cơ sở đầu tiên và chuỗi trong

41 đã kết thúc. Vì hàm

38 trả về một danh sách các chuỗi, nên chúng ta đặt

41 vào một danh sách và trả về nó ❸

Mặt khác, hàm tiếp tục với trường hợp đệ quy. Nếu có thể dấu ngoặc đơn mở vẫn còn ❹, thì hàm gọi

38 với dấu ngoặc đơn mở được thêm vào đối số hiện tại. Nếu còn lại nhiều dấu ngoặc đơn đóng hơn dấu ngoặc đơn mở ❺, thì hàm gọi

38 với dấu ngoặc đơn đóng được thêm vào đối số hiện tại. Việc kiểm tra này đảm bảo rằng một dấu ngoặc đóng chưa khớp sẽ không được thêm vào, vì điều này sẽ làm cho chuỗi không cân bằng, chẳng hạn như dấu ngoặc đóng thứ hai trong

71

Sau các trường hợp đệ quy này là một trường hợp cơ sở vô điều kiện trả về tất cả các chuỗi được trả về từ hai lệnh gọi hàm đệ quy (và tất nhiên, các lệnh gọi hàm đệ quy được thực hiện bởi các lệnh gọi hàm đệ quy này, v.v.) ❻

Bộ nguồn. Tìm tất cả các tập con của một tập hợp

Tập lũy thừa của một tập hợp là tập hợp của mọi tập hợp con có thể có của tập hợp đó. Ví dụ: bộ lũy thừa của {A, B, C} là {{ }, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, { . Điều này tương đương với tập hợp của mọi tổ hợp k có thể có của một tập hợp. Xét cho cùng, tập lũy thừa của {A, B, C} chứa tất cả các tổ hợp 0, tổ hợp 1, tổ hợp 2 và tổ hợp 3 của nó

Nếu bạn đang tìm kiếm một ví dụ trong thế giới thực mà bạn sẽ cần tạo tập sức mạnh của một tập hợp, hãy tưởng tượng một người phỏng vấn xin việc yêu cầu bạn tạo tập hợp sức mạnh của một tập hợp. Về mặt thiên văn, bạn sẽ không cần phải tạo ra sức mạnh của một tập hợp vì bất kỳ lý do nào khác, bao gồm cả công việc bạn đang phỏng vấn

Để tìm mọi lũy thừa của một tập hợp, chúng ta có thể sử dụng lại hàm

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
--snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3',
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP',
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11',
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23',
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ',
--snip--

9 hiện có của mình, gọi nó nhiều lần với mỗi đối số k có thể. Cách tiếp cận này được thực hiện bởi powerSetCombinations. py và powerSetCombinations. các chương trình html trong tệp tài nguyên có thể tải xuống từ https. //Không có tinh bột. com/recursive-book-recursion

Tuy nhiên, chúng ta có thể sử dụng một cách hiệu quả hơn để tạo ra các bộ nguồn. Hãy xem xét bộ lũy thừa của {A, B}, đó là {{A, B}, {A}, {B}, { }}. Bây giờ, giả sử chúng ta thêm một phần tử nữa, C, vào tập hợp và muốn tạo tập hợp sức mạnh của {A, B, C}. Chúng tôi có bốn bộ trong bộ sức mạnh của {A, B} mà chúng tôi đã tạo; . {{A, B, C}, {A, C}, {B, C}, {C}}. hiển thị mẫu về cách thêm nhiều phần tử vào một tập hợp sẽ thêm nhiều tập hợp hơn vào tập hợp sức mạnh của nó

Bảng 6-3. Cách các bộ năng lượng phát triển khi các yếu tố mới (in đậm) được thêm vào bộ

Đặt với phần tử mới Các bộ mới cho bộ nguồnBộ nguồn hoàn chỉnh{ }{ }{{ }}{A}{A}{{ }, {A}}{A, B}{B}, {A, B}{{ }

Tập hợp lũy thừa của các tập hợp lớn hơn tương tự như tập hợp lũy thừa của các tập hợp nhỏ hơn, gợi ý rằng chúng ta có thể tạo một hàm đệ quy để tạo ra chúng. Trường hợp cơ sở là một tập hợp rỗng và tập hợp sức mạnh của nó là một tập hợp chỉ tập hợp trống. Chúng ta có thể sử dụng kỹ thuật head-tail cho hàm đệ quy này. Đối với mỗi phần tử mới mà chúng tôi thêm vào, chúng tôi muốn lấy bộ sức mạnh của đuôi để thêm vào bộ sức mạnh đầy đủ của chúng tôi. Chúng tôi cũng thêm phần tử đầu vào mỗi bộ trong bộ năng lượng đuôi. Cùng với nhau, chúng tạo thành tập hợp sức mạnh đầy đủ cho đối số

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0

Hãy hỏi ba câu hỏi về thuật toán đệ quy về thuật toán tập hợp sức mạnh của chúng ta

Trường hợp cơ sở là gì?
Đối số nào được truyền cho lệnh gọi hàm đệ quy?
Làm thế nào để lập luận này trở nên gần gũi hơn với trường hợp cơ sở?

Hàm đệ quy

78 được triển khai trong powerSet. py

con trăn

5

Mã JavaScript tương đương nằm trong powerSet. html

Các chương trình xuất ra như sau

7

Hàm

78 chấp nhận một đối số duy nhất. chuỗi

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0, chứa các ký tự của bộ ban đầu. Trường hợp cơ sở xảy ra khi

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 là chuỗi trống ❶, đại diện cho một tập rỗng. Nhớ lại rằng tập hợp lũy thừa là tập hợp tất cả các tập hợp con của tập hợp ban đầu. Như vậy, lũy thừa của tập rỗng đơn giản là tập chứa tập rỗng, vì tập rỗng là tập con duy nhất của tập rỗng. Đây là lý do tại sao trường hợp cơ sở trả về

82

Trường hợp đệ quy được chia thành hai phần. Phần đầu tiên là lấy bộ sức mạnh của đuôi của

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0. Chúng tôi sẽ sử dụng nguyên tắc nhảy vọt của niềm tin và chỉ cần giả sử lệnh gọi tới

78 trả về tập hợp sức mạnh của đuôi một cách chính xác ❷, mặc dù tại thời điểm này, chúng tôi vẫn đang trong quá trình viết mã cho

78

Để tạo thành bộ lũy thừa hoàn chỉnh của

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0, phần thứ hai của trường hợp đệ quy tạo thành các bộ mới bằng cách thêm phần đầu vào mỗi bộ lũy thừa đuôi ❸. Cùng với các tập hợp từ phần đầu tiên, điều này tạo thành tập hợp sức mạnh của

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
--snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

0 để trả về ở cuối hàm ❹

Bản tóm tắt

Hoán vị và tổ hợp cũng được đề cập trong các khóa học toán thống kê và xác suất. Bạn có thể tìm thấy đơn vị đếm, hoán vị và tổ hợp của Khan Academy trực tuyến tại https. //www. học viện khan. org/math/thống kê-xác suất/đếm-hoán vị-và-tổ hợp

Có chức năng hoán vị trong Python không?

hàm perm() trong Python dùng để trả về số hoán vị của k mục từ một nhóm n mục , i. e. , nó giúp chúng tôi tìm ra số cách để chúng tôi có thể chọn k mục từ n mục có thứ tự và không lặp lại.

Thuật toán nào tìm thấy tất cả các hoán vị?

Thuật toán của Heap được sử dụng để tạo ra tất cả các hoán vị của n đối tượng. Ý tưởng là tạo ra từng hoán vị từ hoán vị trước đó bằng cách chọn một cặp phần tử để hoán đổi cho nhau mà không làm ảnh hưởng đến n-2 phần tử khác.

Các tham số cho hoán vị trong Python là gì?

Phương thức permutations() tạo ra tất cả các hoán vị của một tập đối tượng cho trước và nhận 2 tham số. Đối tượng và Độ dài , trong đó Độ dài là tùy chọn. Chúng ta có thể chỉ định độ dài hoán vị mong muốn bằng cách chỉ định tham số độ dài.

Hoán vị của ABC trong Python là gì?

Ví dụ xâu ABC có 6 hoán vị, i. e. , ABC, ACB, BAC, BCA, CBA, CAB. Trong Python, chúng ta có thể sử dụng itertools mô-đun tích hợp để lấy hoán vị của các phần tử trong danh sách bằng cách sử dụng hàm permutations() .

programming python