cho python itertools.permutations

Question

Có thể ai đó vui lòng giải thích thuật toán cho itertools.permutations thường quy trong tiêu chuẩn Python lib 2.6 không? Tôi không hiểu tại sao nó hoạt động.

Mã là:

def permutations(iterable, r=None): 
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    # permutations(range(3)) --> 012 021 102 120 201 210 
    pool = tuple(iterable) 
    n = len(pool) 
    r = n if r is None else r 
    if r > n: 
     return 
    indices = range(n) 
    cycles = range(n, n-r, -1) 
    yield tuple(pool[i] for i in indices[:r]) 
    while n: 
     for i in reversed(range(r)): 
      cycles[i] -= 1 
      if cycles[i] == 0: 
       indices[i:] = indices[i+1:] + indices[i:i+1] 
       cycles[i] = n - i 
      else: 
       j = cycles[i] 
       indices[i], indices[-j] = indices[-j], indices[i] 
       yield tuple(pool[i] for i in indices[:r]) 
       break 
     else: 
      return 

Answer 1

Bạn cần phải hiểu lý thuyết toán học của permutation cycles, còn được gọi là "quỹ đạo" (điều quan trọng là phải biết cả hai "về nghệ thuật" kể từ khi đối tượng toán học, trung tâm của combinatorics , là khá tiên tiến, và bạn có thể cần phải tìm kiếm research papers mà có thể sử dụng một hoặc cả hai điều khoản).

Để giới thiệu đơn giản hơn về lý thuyết hoán vị, wikipedia có thể trợ giúp. Mỗi URL mà tôi đã đề cập cung cấp thư mục hợp lý nếu bạn bị thu hút bởi tổ hợp để muốn khám phá thêm và hiểu rõ hơn (tôi đã làm, cá nhân - nó trở thành một sở thích của tôi ;-).

Khi bạn hiểu lý thuyết toán học, mã vẫn tinh tế và thú vị đối với "kỹ sư đảo ngược". Rõ ràng, indices chỉ là hoán vị hiện tại về mặt chỉ số vào hồ bơi, cho rằng các mặt hàng mang lại luôn do

yield tuple(pool[i] for i in indices[:r]) 

Vì vậy, trung tâm của máy móc thiết bị hấp dẫn này là cycles, đại diện quỹ đạo của hoán vị và gây indices phải được cập nhật, chủ yếu là bởi những điều khoản

j = cycles[i] 
indices[i], indices[-j] = indices[-j], indices[i] 

Ie, nếu cycles[i] là j, điều này có nghĩa rằng bản cập nhật bên cạnh các chỉ số là để trao đổi một thứ i (từ trái sang) với một k-th từ bên phải (ví dụ: nếu j là 1 thì yếu tố cuối cùng của indices đang được đổi chỗ - indices[-1]). Và sau đó có ít thường xuyên "số lượng lớn cập nhật" khi một mục của cycles đạt 0 trong suất này của nó:

indices[i:] = indices[i+1:] + indices[i:i+1] 
cycles[i] = n - i 

này đặt mục thứ i của indices ở phút cuối, chuyển tất cả các mục sau đây của chỉ số này sang bên trái và cho biết rằng lần tới khi chúng tôi đến mục này là cycles, chúng tôi sẽ hoán đổi mặt hàng mới i thứ indices (từ bên trái) với số n - i thứ (từ bên phải) - đó sẽ là i một lần nữa, ngoại trừ khóa học cho thực tế là sẽ có

cycles[i] -= 1 

trước khi chúng tôi kiểm tra tiếp theo ;-).

Phần cứng dĩ nhiên sẽ là chứng minh hoạt động - tức là tất cả các hoán vị được tạo ra một cách toàn diện, không trùng lặp và thoát "đúng giờ". Tôi nghĩ rằng, thay vì bằng chứng, có thể dễ dàng hơn để xem cách máy móc hoạt động như thế nào khi được phơi nhiễm hoàn toàn trong các trường hợp đơn giản - đưa ra các câu hỏi yield và thêm print (Python 2.*), Chúng tôi có

def permutations(iterable, r=None): 
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    # permutations(range(3)) --> 012 021 102 120 201 210 
    pool = tuple(iterable) 
    n = len(pool) 
    r = n if r is None else r 
    if r > n: 
     return 
    indices = range(n) 
    cycles = range(n, n-r, -1) 
    print 'I', 0, cycles, indices 
    # yield tuple(pool[i] for i in indices[:r]) 
    print indices[:r] 
    while n: 
     for i in reversed(range(r)): 
      cycles[i] -= 1 
      if cycles[i] == 0: 
     print 'B', i, cycles, indices 
       indices[i:] = indices[i+1:] + indices[i:i+1] 
       cycles[i] = n - i 
     print 'A', i, cycles, indices 
      else: 
     print 'b', i, cycles, indices 
       j = cycles[i] 
       indices[i], indices[-j] = indices[-j], indices[i] 
     print 'a', i, cycles, indices 
       # yield tuple(pool[i] for i in indices[:r]) 
      print indices[:r] 
       break 
     else: 
      return 

permutations('ABC', 2) 

Chạy điều này cho thấy:

I 0 [3, 2] [0, 1, 2] 
[0, 1] 
b 1 [3, 1] [0, 1, 2] 
a 1 [3, 1] [0, 2, 1] 
[0, 2] 
B 1 [3, 0] [0, 2, 1] 
A 1 [3, 2] [0, 1, 2] 
b 0 [2, 2] [0, 1, 2] 
a 0 [2, 2] [1, 0, 2] 
[1, 0] 
b 1 [2, 1] [1, 0, 2] 
a 1 [2, 1] [1, 2, 0] 
[1, 2] 
B 1 [2, 0] [1, 2, 0] 
A 1 [2, 2] [1, 0, 2] 
b 0 [1, 2] [1, 0, 2] 
a 0 [1, 2] [2, 0, 1] 
[2, 0] 
b 1 [1, 1] [2, 0, 1] 
a 1 [1, 1] [2, 1, 0] 
[2, 1] 
B 1 [1, 0] [2, 1, 0] 
A 1 [1, 2] [2, 0, 1] 
B 0 [0, 2] [2, 0, 1] 
A 0 [3, 2] [0, 1, 2] 

Focus on the cycles: họ bắt đầu như 3, 2 - sau đó người cuối cùng được giảm đi, vì vậy 3, 1 - cuối cùng không phải là số không vì vậy chúng tôi có một sự kiện "nhỏ" (một trao đổi trong các chỉ số) và phá vỡ vòng lặp bên trong. Sau đó, chúng ta nhập lại lần nữa, lần này sự giảm của lần cuối cho 3, 0 - số cuối cùng bằng 0, do đó nó là sự kiện "lớn" - "trao đổi hàng loạt" trong các chỉ mục (không có nhiều khối lượng ở đây, nhưng, có thể có ;-) và chu trình quay trở lại 3, 2. Nhưng bây giờ chúng tôi đã không phá vỡ vòng lặp for, vì vậy chúng tôi tiếp tục bằng cách giảm số tiếp theo -to-last (trong trường hợp này, lần đầu tiên) - cho một sự kiện nhỏ, một sự hoán đổi trong các chỉ số, và chúng ta phá vỡ vòng lặp bên trong một lần nữa. Quay lại vòng lặp, nhưng lần nữa cái cuối cùng bị giảm đi, lần này cho sự kiện thứ 2, 1 - nhỏ, v.v. Cuối cùng toàn bộ vòng lặp chỉ xảy ra với các sự kiện lớn, không có sự kiện nhỏ - đó là khi các chu kỳ bắt đầu như tất cả , do đó, giảm xuống mỗi số không (sự kiện lớn), không có yield xảy ra vào chu kỳ cuối cùng đó.

Vì không có break được thực hiện trong chu kỳ đó, chúng tôi lấy chi nhánh else của số for, trả về. Lưu ý rằng while n có thể gây hiểu lầm một chút: nó thực sự hoạt động như một while True - n không bao giờ thay đổi, vòng lặp while chỉ thoát khỏi tuyên bố return đó; nó cũng có thể được biểu thị bằng if not n: return theo sau là while True:, bởi vì dĩ nhiên khi n là 0 (trống "hồ bơi") thì không có gì nhiều hơn để sinh lợi sau lần đầu tiên, tầm thường rỗng yield. Tác giả vừa quyết định lưu một vài dòng bằng cách thu gọn séc if not n: bằng số while ;-).

Tôi khuyên bạn nên tiếp tục bằng cách kiểm tra thêm một vài trường hợp cụ thể - cuối cùng bạn sẽ cảm nhận được hoạt động "đồng hồ" hoạt động. Tập trung vào chỉ cycles lúc đầu (có thể chỉnh sửa các tuyên bố print cho phù hợp, loại bỏ indices từ chúng), vì tiến trình giống như đồng hồ của chúng thông qua quỹ đạo của chúng là chìa khóa cho thuật toán tinh tế và sâu sắc này; một khi bạn grok rằng, cách indices được cập nhật đúng cách để đáp ứng với trình tự của cycles gần như là một anticlimax -!)

Answer 2

Nó là dễ dàng hơn để trả lời với một mô hình trong các kết quả hơn lời nói (trừ bạn muốn biết phần toán học của lý thuyết), vì vậy bản in ra sẽ là cách tốt nhất để giải thích.
Điều tinh tế nhất là, sau khi kết thúc đến cuối, nó sẽ tự đặt lại đến lượt đầu tiên của vòng cuối cùng và bắt đầu vòng lặp tiếp theo hoặc liên tục đặt lại thành lượt đầu tiên của vòng cuối cùng lớn hơn như một chiếc đồng hồ.

Phần mã làm công việc thiết lập lại:

  if cycles[i] == 0: 
      indices[i:] = indices[i+1:] + indices[i:i+1] 
      cycles[i] = n - i 

toàn:

In [54]: def permutations(iterable, r=None): 
    ...:  # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    ...:  # permutations(range(3)) --> 012 021 102 120 201 210 
    ...:  pool = tuple(iterable) 
    ...:  n = len(pool) 
    ...:  r = n if r is None else r 
    ...:  if r > n: 
    ...:   return 
    ...:  indices = range(n) 
    ...:  cycles = range(n, n-r, -1) 
    ...:  yield tuple(pool[i] for i in indices[:r]) 
    ...:  print(indices, cycles) 
    ...:  while n: 
    ...:   for i in reversed(range(r)): 
    ...:    cycles[i] -= 1 
    ...:    if cycles[i] == 0: 
    ...:     indices[i:] = indices[i+1:] + indices[i:i+1] 
    ...:     cycles[i] = n - i 
    ...:     print("reset------------------") 
    ...:     print(indices, cycles) 
    ...:     print("------------------") 
    ...:    else: 
    ...:     j = cycles[i] 
    ...:     indices[i], indices[-j] = indices[-j], indices[i] 
    ...:     print(indices, cycles, i, n-j) 
    ...:     yield tuple(pool[i] for i in indices[:r]) 
    ...:     break 
    ...:   else: 
    ...:    return 

một phần của kết quả:

In [54]: list(','.join(i) for i in permutations('ABCDE', 3)) 
([0, 1, 2, 3, 4], [5, 4, 3]) 
([0, 1, 3, 2, 4], [5, 4, 2], 2, 3) 
([0, 1, 4, 2, 3], [5, 4, 1], 2, 4) 
reset------------------ 
([0, 1, 2, 3, 4], [5, 4, 3]) 
------------------ 
([0, 2, 1, 3, 4], [5, 3, 3], 1, 2) 
([0, 2, 3, 1, 4], [5, 3, 2], 2, 3) 
([0, 2, 4, 1, 3], [5, 3, 1], 2, 4) 
reset------------------ 
([0, 2, 1, 3, 4], [5, 3, 3]) 
------------------ 
([0, 3, 1, 2, 4], [5, 2, 3], 1, 3) 
([0, 3, 2, 1, 4], [5, 2, 2], 2, 3) 
([0, 3, 4, 1, 2], [5, 2, 1], 2, 4) 
reset------------------ 
([0, 3, 1, 2, 4], [5, 2, 3]) 
------------------ 
([0, 4, 1, 2, 3], [5, 1, 3], 1, 4) 
([0, 4, 2, 1, 3], [5, 1, 2], 2, 3) 
([0, 4, 3, 1, 2], [5, 1, 1], 2, 4) 
reset------------------ 
([0, 4, 1, 2, 3], [5, 1, 3]) 
------------------ 
reset------------------(bigger reset) 
([0, 1, 2, 3, 4], [5, 4, 3]) 
------------------ 
([1, 0, 2, 3, 4], [4, 4, 3], 0, 1) 
([1, 0, 3, 2, 4], [4, 4, 2], 2, 3) 
([1, 0, 4, 2, 3], [4, 4, 1], 2, 4) 
reset------------------ 
([1, 0, 2, 3, 4], [4, 4, 3]) 
------------------ 
([1, 2, 0, 3, 4], [4, 3, 3], 1, 2) 
([1, 2, 3, 0, 4], [4, 3, 2], 2, 3) 
([1, 2, 4, 0, 3], [4, 3, 1], 2, 4)