Cách bộ nhớ hiệu quả nhất để tạo ra sự kết hợp của một bộ trong python là gì?

Question

Đây là mã tôi đã đưa ra:

def combinations(input): 
    ret = [''] 
    for i in range(len(input)): 
     ret.extend([prefix+input[i] for prefix in ret]) 
    return ret 

thuật toán này là O (2^n) thời gian, nhưng không gian có thể giảm? Tôi đã nghe sử dụng yield có thể hoạt động nhưng gặp sự cố khi suy nghĩ qua cách triển khai với yield. Vui lòng không sử dụng chức năng kết hợp được tích hợp sẵn - Tôi muốn xem nó được triển khai như thế nào.

Answer 1

Câu hỏi của bạn đặc biệt nói rằng bạn muốn xem những gì mã sẽ như thế nào, vì vậy đây là một mã ví dụ bàn tay của một O (n) giải pháp không gian:

def combinations(input_list, acc=''): 

    if not input_list: 
     yield acc 
     return 

    next_val = input_list[0] 

    for rest in combinations(input_list[1:], acc): 
     yield rest 

    acc += next_val 

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)" 
    for rest in combinations(input_list[1:], acc): 
     yield rest 

Lưu ý rằng số học chuỗi con có thể rất tốn kém (vì nó có để sao chép chuỗi nhiều lần), vì vậy đây là một phiên bản nhẹ hiệu quả hơn về sự phức tạp:

def combinations(input_list, acc='', from_idx=0): 

    if len(input_list) <= from_idx: 
     yield acc 
     return 

    next_val = input_list[from_idx] 

    for rest in combinations(input_list, acc, from_idx + 1): 
     yield rest 

    acc += next_val 

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)" 
    for rest in combinations(input_list, acc, from_idx + 1): 
     yield rest 

tôi không sử dụng Python 3.2, nhưng nếu bạn là bạn có thể viết nó như thế này:

def combinations(input_list, acc='', from_idx=0): 

    if len(input_list) <= from_idx: 
     yield acc 
     return 

    next_val = input_list[from_idx] 

    yield from combinations(input_list, acc, from_idx + 1) 
    acc += next_val 
    yield from combinations(input_list, acc, from_idx + 1) 

Tôi cũng nên lưu ý rằng đây hoàn toàn là học từ itertools.combinations làm một công việc tốt và làm việc cho một rộng hơn mảng đầu vào (bao gồm các biểu thức máy phát).

Answer 2

Something như thế này nên làm điều đó:

>>> print list(itertools.combinations({1, 2, 3, 4}, 3)) 
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)] 
>>> 

Answer 3

Bạn có thể sử dụng yield trong mã của bạn như sau:

def combinations(input): 
    ret = [''] 
    yield '' 
    for i in range(len(input)): 
     for prefix in ret: 
      combination = prefix+input[i] 
      ret.extend(combination) 
      yield combination 

Nhưng nó không giúp bạn tiết kiệm không gian bất kỳ.

itertools.combinations documentation hiển thị một (nhiều) thuật toán phức tạp hơn hoạt động trong không gian cố định - actual implementation là trong C, nhưng tuyên bố là tương đương.