Bellek etkin güç kipi algoritması

Question

9 harfli 'ABCDEFGHI' dizesinin tüm alt kümelerini (power set) hesaplamaya çalışılıyor.

Standart özyinelemeli yöntemleri kullanarak, makinem tamamlamadan önce bellek yetersiz (1GB) hatası veriyor. Daha fazla fiziksel belleğim yok.

Bu nasıl daha iyi yapılabilir? Dil bir sorun değildir ve standart çıktıya gönderilen sonuçlar da iyidir - çıktı almadan önce bellekte tutulması gerekmez.

Answer 1

gücü kümesinden önemsiz örten eşleme vardır X = {A, B, C, D, E, F, G, H, I} 0 ile 2 arasındaki sayı kümesine. | ​​X | = 2^9:

çap harita (taban 2) 000000000 için

{A} 100000000 eşleştiren (taban 2)

{B} 010000000 eşleştiren (taban 2)

{ C} 001000000 (taban 2)

... eşleştiren

{I} 000000001 eşleştiren (baz 2)

{A, B} 110,000,000 (2 tabanı)

{A, C} 101000000 eşleştiren (taban 2)

... eşleştiren

{A, B, C, D, E, Eğer önlemek Bu şekilde

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 
} 

: F, G, H, I} Bu (yalancı kod) gibi set gücü oluşturmak için bu gözlemi kullanabilirsiniz

111111111 (taban 2) eşleştiren herhangi bir özyineleme (ve neye ihtiyacın olduğuna bağlı olarak) Bunun için, birçok veri yapısını tahsis etmeden powerset'i "üretebilir" - örneğin, yalnızca güç setini yazdırmanız gerekiyorsa).

Answer 2

Bunun için bölünmeyi kullanmak ve fethetmek olacaktır:

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

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

Bu şekilde, hemen çözümlerin sayısı 2 olduğunu görüyoruz^| originalSet | - bu yüzden "güç seti" deniyor. Sizin durumunuzda, bu 2^9 olacaktır, bu yüzden 1GB'lık bir makinede hafıza yetersizliği olmamalıdır. Algoritmanızda bazı hataların olduğunu tahmin ediyorum.

Answer 3

Bu çalıştı olduğunu doğrulamıştır:

#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

biraz şeması çözümü

(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))))) 

Veya R5RS Şemasında

, daha fazla alan verimli versiyon

(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

Nasıl bu zarif çözümü hakkında? R = 1 olana kadar yinelenecek nCr üreten kodu genişletin!

#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; 
} 

Çıkış:

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