продукты значений в каждом наборе Powerset

Учитывая массив, позволяет сказать, что массив = [1,2,3]продукты значений в каждом наборе Powerset

Я хочу, чтобы выяснить, все значения продуктов в каждом наборе его Powerset.

Например,

Набор мощности

{null} 
{1} - 1 
{2} - 2 
{3} - 3 
{1,2}- 2 
{2,3}- 6 
{1,3}- 3 
{1,2,3}- 6

Обозначения: набор с последующим произведением значений в наборе

Как можно достичь этого с помощью динамического программирования.

Примечание:

Я попробовал этот путь, нашел Powerset по

void printPowerSet(int *set, int set_size) 
{ 
    /*set_size of power set of a set with set_size 
     n is (2**n -1)*/ 
    unsigned int pow_set_size = pow(2, set_size); 
    int counter, j; 

    /*Run from counter 000..0 to 111..1*/ 
    for(counter = 0; counter < pow_set_size; counter++) 
    { 

    int product=1; 
     for(j = 0; j < set_size; j++) 
     { 
      /* Check if jth bit in the counter is set 
      If set then pront jth element from set */ 
      if(counter & (1<<j)) 
      product *= counter; 
     } 
     printf("%d", product); 
    } 
}

Эта техника работает абсолютно нормально, но для небольших массивов (размер массива < 32)

источник

2013-08-06 user650521

Я сомневаюсь, что DP (buttom-up) улучшит ответ, идея DP обычно создает все возможности из от более низкого до более высокого и маркировки, которые действительны. Однако здесь диапазон возможностей «[1, x1 * x2 * ... * xn]» - что намного хуже, чем '2^n', предполагая, что все (кроме одного значения) 'x_i> = 2'. – amit

@amit: Ну, он не должен этого делать, вы не будете использовать все в этом диапазоне. Есть способ сделать это, который в худшем случае использует количество различных (ну, 'O (количество отдельных продуктов)') –

@ DennisMeng как мы можем достичь этого в O (количество отдельных продуктов) – user650521

Пусть ваш вклад набор S и имеет size элементов. Что-то, как это будет работать:

make an empty set A 
for every element s in S { 
    make an empty set B 
    for every t in A { 
     add s*t to B 
    } 
    A = union of A and B 
}

Общая память используется сразу тогда в худшем случае сумма размеров обоих наборов, так O(number of distinct products)). Ваша «подзадача» будет «Каковы продукты, которые я могу получить, используя первые x элементов набора?

источник

2013-08-06 17:08:50

продукты значений в каждом наборе Powerset

ответ

Смежные вопросы