Thuật toán cho itertools.combinations trong Python

Question

Tôi đã giải quyết một câu đố lập trình liên quan đến kết hợp. Nó dẫn tôi đến một chức năng tuyệt vời itertools.combinations và tôi muốn biết nó hoạt động như thế nào dưới mui xe. Tài liệu nói rằng các thuật toán tương đương với những điều sau đây:

def combinations(iterable, r): 
    # combinations('ABCD', 2) --> AB AC AD BC BD CD 
    # combinations(range(4), 3) --> 012 013 023 123 
    pool = tuple(iterable) 
    n = len(pool) 
    if r > n: 
     return 
    indices = list(range(r)) 
    yield tuple(pool[i] for i in indices) 
    while True: 
     for i in reversed(range(r)): 
      if indices[i] != i + n - r: 
       break 
     else: 
      return 
     indices[i] += 1 
     for j in range(i+1, r): 
      indices[j] = indices[j-1] + 1 
     yield tuple(pool[i] for i in indices) 

Tôi có ý tưởng: chúng ta bắt đầu với sự kết hợp rõ ràng nhất (r yếu tố đầu tiên liên tiếp). Sau đó, chúng tôi thay đổi một (cuối) mục để có được mỗi sự kết hợp tiếp theo.

Điều tôi đang gặp phải là vòng lặp có điều kiện bên trong for.

for i in reversed(range(r)): 
    if indices[i] != i + n - r: 
     break 

Thử nghiệm này là rất ngắn và tôi nghi ngờ đó là nơi tất cả các phép thuật xảy ra. Xin vui lòng, cho tôi một gợi ý để tôi có thể tìm ra.

Answer 1

Vòng lặp có hai mục đích:

1. Chấm dứt nếu người cuối cùng chỉ số danh sách đã đạt
2. Xác định vị trí bên phải nhất trong danh sách chỉ mục có thể được tăng lên một cách hợp pháp. Vị trí này sau đó là điểm bắt đầu để đặt lại tất cả các phân ở bên phải.

Giả sử bạn có thể lặp lại trên 5 phần tử và muốn kết hợp độ dài 3. Điều cơ bản bạn cần là tạo danh sách chỉ mục.Phần ngon ngọt của thuật toán trên tạo ra tiếp theo đó chỉ số danh sách từ hiện thời:

# obvious 
index-pool:  [0,1,2,3,4] 
first index-list: [0,1,2] 
        [0,1,3] 
        ... 
        [1,3,4] 
last index-list: [2,3,4] 

i + n - r là giá trị tối đa cho chỉ số i trong chỉ mục-list:

index 0: i + n - r = 0 + 5 - 3 = 2 
index 1: i + n - r = 1 + 5 - 3 = 3 
index 2: i + n - r = 2 + 5 - 3 = 4 
# compare last index-list above 

=>

for i in reversed(range(r)): 
    if indices[i] != i + n - r: 
     break 
else: 
    break 

này vòng ngược qua curre nt index-list và dừng ở vị trí đầu tiên không giữ giá trị chỉ số tối đa của nó. Nếu tất cả các vị trí giữ giá trị chỉ số tối đa của chúng, thì không có danh sách chỉ mục nào khác, do đó, return.

Trong trường hợp chung là [0,1,4] người ta có thể xác minh rằng danh sách tiếp theo phải là [0,2,3]. Vòng lặp dừng lại ở vị trí 1, mã tiếp theo

indices[i] += 1 

tăng giá trị cho indeces[i] (1 -> 2). Cuối cùng

for j in range(i+1, r): 
    indices[j] = indices[j-1] + 1 

resets tất cả các vị trí > i đến chỉ số giá trị pháp lý nhỏ nhất, mỗi 1 lớn hơn người tiền nhiệm của nó.

Answer 2

Điều này cho vòng lặp thực hiện một điều đơn giản: nó kiểm tra xem thuật toán có nên chấm dứt hay không.

Thuật toán bắt đầu với r mục đầu tiên và tăng cho đến khi nó đạt đến r mục cuối cùng trong iterable, đó là [Sn-r+1 ... Sn-1, Sn] (nếu chúng ta để S là iterable).

Bây giờ, các thuật toán quét tất cả các mục trong các chỉ số, và chắc chắn rằng họ vẫn phải đi đâu - vì vậy nó xác minh indice thứ i là không chỉ số n - r + i, mà theo đoạn trước là (chúng ta bỏ qua 1 ở đây vì danh sách là 0-based).

Nếu tất cả các chỉ số này bằng với các vị trí r cuối cùng - sau đó nó đi vào else, cam kết return và chấm dứt thuật toán.

---

Chúng ta có thể tạo ra các chức năng tương tự bằng cách sử dụng

if indices == list(range(n-r, n)): return 

nhưng lý do chính của việc này "mớ hỗn độn" (sử dụng reverse và break) là chỉ số đầu tiên từ cuối cùng mà không phù hợp được lưu bên trong i và được sử dụng cho cấp độ tiếp theo của thuật toán tăng chỉ mục này và đảm bảo thiết lập lại phần còn lại.

---

Bạn có thể kiểm tra điều này bằng cách thay thế yield s với

print('Combination: {} Indices: {}'.format(tuple(pool[i] for i in indices), indices)) 

Answer 3

Source code có một số thông tin bổ sung về những gì đang diễn ra.

Các yeild tuyên bố trước while loop trả về một kết hợp của các yếu tố tầm thường (mà chỉ đơn giản là r yếu tố đầu tiên của A, (A[0], ..., A[r-1])) và chuẩn bị indices cho công việc trong tương lai. Giả sử chúng ta có A='ABCDE' và r=3. Sau đó, sau bước đầu tiên, giá trị của indices là [0, 1, 2], trỏ đến ('A', 'B', 'C').

Hãy nhìn vào mã nguồn của vòng lặp trong câu hỏi:

2160   /* Scan indices right-to-left until finding one that is not 
2161    at its maximum (i + n - r). */ 
2162   for (i=r-1 ; i >= 0 && indices[i] == i+n-r ; i--) 
2163    ; 

Vòng lặp này tìm kiếm cho các phần tử ngoài cùng bên phải của indices đã không đạt được giá trị lớn nhất từ ​​trước đến nay. Sau tuyên bố đầu tiên của yield giá trị của indices là [0, 1, 2]. Do đó, vòng kết nối for sẽ kết thúc tại indices[2].

Tiếp theo, đoạn mã sau increments yếu tố i thứ của indices:

2170   /* Increment the current index which we know is not at its 
2171    maximum. Then move back to the right setting each index 
2172    to its lowest possible value (one higher than the index 
2173    to its left -- this maintains the sort order invariant). */ 
2174   indices[i]++; 

Kết quả là, chúng tôi nhận chỉ số kết hợp [0, 1, 3], mà điểm đến ('A', 'B', 'D').

Sau đó, chúng tôi quay trở lại các chỉ số tiếp theo nếu họ là quá lớn:

2175   for (j=i+1 ; j<r ; j++) 
2176    indices[j] = indices[j-1] + 1; 

Chỉ số tăng từng bước:

bước chỉ số

1. (0, 1, 2)
2. (0, 1, 3)
3. (0, 1, 4)
4. (0, 2, 3)
5. (0, 2, 4)
6. (0, 3, 4)
7. (1, 2, 3) ...