Алгоритм эффективного набора памяти

Question

Попытка вычислить все подмножества ( набор мощности ) 9-буквенной строки 'ABCDEFGHI'.

Используя стандартные рекурсивные методы, моя машина выходит из памяти (1GB)до завершения.У меня больше нет физической памяти.

Как это можно сделать лучше?Язык не имеет значения, и результаты, отправляемые на стандартный вывод, также хороши - его не нужно хранить в памяти перед выводом.

Answer 1

Существует тривиальное биективное отображение из набора степеней X = {A, B, C, D, E, F, G, H, I} в набор чисел между 0 и 2 ^ | X | = 2 ^ 9:

Ø отображается на 000000000 (база 2)

{A} соответствует 100000000 (база 2)

{B} соответствует 010000000 (база 2)

{C} соответствует 001000000 (база 2)

...

{I} соответствует 000000001 (база 2)

{A, B} соответствует 110000000 (база 2)

{A, C} соответствует 101000000 (база 2)

...

{A, B, C, D, E, F, G, H, I} соответствует 111111111 (база 2)

Вы можете использовать это наблюдение для создания набора мощности, подобного этому (псевдокод):

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
}

Таким образом, вы избегаете любой рекурсии (и, в зависимости от того, для чего вам нужен блок питания, вы можете даже иметь возможность «генерировать» блок питания без выделения большого количества структур данных - например, если вам просто нужно распечатать набор мощности).

Answer 2

небольшое решение схемы

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

Или в схеме R5RS, более экономичная версия

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

Я бы использовал для этого «разделяй и властвуй»:

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

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

Таким образом, вы сразу видите, что число решений равно 2 ^ | originalSet |- Вот почему это называется «набор мощности».В вашем случае это будет 2 ^ 9, поэтому не должно быть ошибки нехватки памяти на машине с 1 ГБ.Я полагаю, у вас есть ошибка в вашем алгоритме.

Answer 4

Как насчет этого элегантного решения?Расширить код, который генерирует nCr для итерации для r = 1 до 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;
}

Выход:

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 

Answer 5

Я убедился, что это сработало:

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