Thuật toán bộ công suất hiệu quả bộ nhớ

Question

Đang cố gắng tính toán tất cả các tập con (power set) của chuỗi 9 chữ cái 'ABCDEFGHI'.

Sử dụng các phương pháp đệ quy chuẩn, máy của tôi bị lỗi hết bộ nhớ (1GB) trước khi hoàn thành. Tôi không còn ký ức vật lý nữa.

Làm cách nào để thực hiện điều này tốt hơn? Ngôn ngữ là không có vấn đề và kết quả gửi đến đầu ra tiêu chuẩn cũng tốt - nó không cần phải được giữ tất cả trong bộ nhớ trước khi xuất ra.

Answer 1

Có một ánh xạ song ánh tầm thường từ bộ sức mạnh của X = {A, B, C, D, E, F, G, H, I} đến tập hợp các số từ 0 đến 2^| X | = 2^9:

bản đồ Ø tới 000000000 (cơ sở 2)

{A} bản đồ để 100000000 (cơ sở 2)

{B} bản đồ để 010.000.000 (cơ sở 2)

{ C} bản đồ để 001000000 (cơ sở 2)

...

{I} bản đồ để 000.000.001 (cơ sở 2)

{A, B} bản đồ để 110.000.000 (cơ sở 2)

{A, C} bản đồ để 101.000.000 (cơ sở 2)

...

{A, B, C, D, E , F, G, H, I} bản đồ để 111111111 (cơ sở 2)

bạn có thể sử dụng quan sát này để tạo sức mạnh thiết lập như thế này (pseudo-code):

Set powerset = new Set(); 
for(int i between 0 and 2^9) 
{ 
    Set subset = new Set(); 
    for each enabled bit in i add the corresponding letter to subset 
    add subset to powerset 
} 

Bằng cách này bạn tránh bất kỳ đệ quy nào (và tùy thuộc vào những gì bạn cần thiết lập cho, bạn thậm chí có thể "tạo ra" các quyền hạn mà không cần phân bổ nhiều cấu trúc dữ liệu - ví dụ, nếu bạn chỉ cần in ra bộ điện).

Answer 2

Tôi sẽ sử dụng phân chia và chinh phục cho điều này:

Set powerSet(Set set) { 
    return merge(powerSet(Set leftHalf), powerSet(Set rightHalf)); 
} 

merge(Set leftHalf, Set rightHalf) { 
    return union(leftHalf, rightHalf, allPairwiseCombinations(leftHalf, rightHalf)); 
} 

Bằng cách đó, bạn ngay lập tức thấy rằng số lượng các giải pháp là 2^| originalSet | - đó là lý do tại sao nó được gọi là "bộ nguồn". Trong trường hợp của bạn, điều này sẽ là 2^9, do đó, không nên có lỗi hết bộ nhớ trên máy 1GB. Tôi đoán bạn có một số lỗi trong thuật toán của bạn.

Answer 3

Tôi xác nhận rằng đây làm việc tốt:

#include <iostream> 

void print_combination(char* str, char* buffer, int len, int num, int pos) 
{ 
    if(num == 0) 
    { 
    std::cout << buffer << std::endl; 
    return; 
    } 

    for(int i = pos; i < len - num + 1; ++i) 
    { 
    buffer[num - 1] = str[i]; 
    print_combination(str, buffer, len, num - 1, i + 1); 
    } 
} 

int main() 
{ 
    char str[] = "ABCDEFGHI"; 
    char buffer[10]; 
    for(auto i = 1u; i <= sizeof(str); ++i) 
    { 
    buffer[i] = '\0'; 
    print_combination(str, buffer, 9, i, 0); 
    } 
} 

Answer 4

một giải pháp chương trình ít

(define (power_set_iter set) 
    (let loop ((res '(())) 
      (s set)) 
    (if (empty? s) 
     res 
     (loop (append (map (lambda (i) 
          (cons (car s) i)) 
          res) 
         res) 
       (cdr s))))) 

Hoặc trong R5RS Đề án, nhiều không gian hiệu quả phiên bản

(define (pset s) 
    (do ((r '(())) 
     (s s (cdr s))) 
     ((null? s) r) 
    (for-each 
     (lambda (i) 
     (set! r (cons (cons (car s) i) 
         r))) 
     (reverse r)))) 

Answer 5

Làm thế nào về giải pháp thanh lịch này? Mở rộng mã tạo nCr để lặp lại cho r = 1 cho đến n!

#include<iostream> 
using namespace std; 

void printArray(int arr[],int s,int n) 
{ 
    cout<<endl; 
    for(int i=s ; i<=n-1 ; i++) 
     cout<<arr[i]<<" "; 
} 

void combinateUtil(int arr[],int n,int i,int temp[],int r,int index) 
{ 
    // What if n=5 and r=5, then we have to just print it and "return"! 
    // Thus, have this base case first! 
    if(index==r) 
    { 
     printArray(temp,0,r); 
     return; 
    } 

    // If i exceeds n, then there is no poin in recurring! Thus, return 
    if(i>=n) 
     return; 


    temp[index]=arr[i]; 
    combinateUtil(arr,n,i+1,temp,r,index+1); 
    combinateUtil(arr,n,i+1,temp,r,index); 

} 

void printCombinations(int arr[],int n) 
{ 
    for(int r=1 ; r<=n ; r++) 
    { 
     int *temp = new int[r]; 
     combinateUtil(arr,n,0,temp,r,0); 
    } 
} 



int main() 
{ 
    int arr[] = {1,2,3,4,5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    printCombinations(arr,n); 

    cin.get(); 
    cin.get(); 
    return 0; 
} 

Các Output:

1 
2 
3 
4 
5 
1 2 
1 3 
1 4 
1 5 
2 3 
2 4 
2 5 
3 4 
3 5 
4 5 
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
1 2 3 4 
1 2 3 5 
1 2 4 5 
1 3 4 5 
2 3 4 5 
1 2 3 4 5