Teniendo en cuenta la suma de elementos de todos los $2^n$ subconjuntos de un conjunto múltiple con $n$ elementos, encontrar los elementos de la multiset.

Question

Por multiset, me refiero a un conjunto que puede se repiten elementos.

Estoy buscando un algoritmo de este problema.

Edición: Son los elementos de la dada multiset > = 0.

Edit2: Ejemplo: dado {0, 1, 3, 3, 4, 4, 6, 7}, la salida debería ser {1, 3, 3}

Answer 1

Deje $A$ ser el conjunto original, y $S$ el conjunto de las sumas.

Considere el siguiente proceso:

Deje $A_0 = \{\}$, y deje $S_0 = S \setminus \{0\}$.

En cada paso, vamos a $A_{i + 1} = A_{i} \cup \min S_i$, y deje $S_{i + 1} = S \setminus P_{i + 1}$ donde $P_i$ es el conjunto múltiple de la suma de la potencia de conjunto de $A_i$.

Tenga en cuenta que en cada paso, $\min S_i$ debe ser en $A$, ya que no se genera como la suma de los elementos más pequeños de $A$.

Por lo tanto, $A_n = A$.

Edit: he Aquí una implementación de Python que se ejecuta en $O(n \cdot 2^n)$ del tiempo.

def log_set(power_set_sums):
    s = power_set_sums[:]
    heapq.heapify(s)

    a = []
    p = [0]

    to_delete = [0]

    while s:
        x = heapq.heappop(s)
        if to_delete and to_delete[0] == x:
            heapq.heappop(to_delete)
        else:
            a.append(x)
            for i, y in enumerate(p[:]):
                p.append(x + y)
                if i != 0:
                    heapq.heappush(to_delete, x + y)

    return a

Answer 2

Existe una implementación del algoritmo de Mnemónico

• el primer elemento es tomado y negada
• en cada iteración, el 1er elemento positivo de la toma. A continuación, se añade a todo lo anterior negado elementos para que las banderas de la nueva sumas mediante la negación de ellos.

Podemos tomar la 1ª opción, ya que es , en este paso , el más bajo, que no es una suma de los valores anteriores. No se puede no más ser una suma de los siguientes valores, entonces es un valor de la raíz.

Para ejecutar el script , copiar pegar en el bloc de notas , la herramienta de firefox o algo similar y hacer un Ctrl L. La última variable a modificar es de salida.

function devloop(n,sett)
{
    var ret = [0] ;
    for( var i = 0 ; i < sett.length ; i ++ )
    {
        lret = ret.length ;
        for( var j = 0 ; j < lret ; j ++ )
        {
            ret.push( ret[j]+sett[i] ) ;
        }
    }

    return ret.sort(function(a, b){return a-b}) ;
}
function remsum(ords,newd,start)
{
    var i , j , val ;
// heavy and somehow brute ! must record a state with more than 2 values
    var ords2 = []; 
    for( i = 0 ; i < ords.length ; i++ )
    {
        ords2[i]  = ords[i]; 
        if( ords[i] <= 0 )
        {
            ords2.push(ords[i]); 
        }
    }

    for( j = 0 ;  j < ords2.length ; j++ )
    {
        val = newd-ords2[j] ;
        for( i = start ;  i < ords.length  ; i++ )
        {
            if( ords[i] == val )
            {
                ords[i] = -ords[i] ;
                start = i + 1 ;
                break ;
            }
        }
    }
    return  ords ;
}


function main(ordsum,n)
{
    var lordsum = ordsum.length , lordsum2 = lordsum/2 , sett=[ ordsum[1] ] , ok = false , found = 1 ,i ;
    // remove 1 time ordsum[1]
    ordsum[ 1 ] = -ordsum[ 1 ] ;

    for( i = 2 ;  found < n && i <= lordsum ; i ++)
    {
        if( ordsum[i] > 0 )
        {
            sett.push( ordsum[i] ) ;
            ordsum = remsum(ordsum,ordsum[i],i) ;
            found ++ ;
        }
    }
    return sett;
}
//  var ordsumE = [0, 1, 3, 3, 4, 4, 6, 7] , nE = 3 ;

// argum of the test

var res="", trvE , nE ;

var trvEListe = [
// 1st test
        [1,2,3,6,12,14,26] ,

// 2nd test
        [1,2,3,6,9,11,12,14,26] ,

// 3rd test
        [1,2,2,6,8,10,10,12,13,14,26] ,

// 4th test
        [1,1,2,2,2,6,8,10,10,10,13,14,126]
        ] ;

for( var nn = 0 ; nn < 4 ; nn ++ )
{
    trvE = trvEListe[nn] ;
    nE = trvE.length ;

// res = the output
    res += ("\n\nthe list to find :\n\t"+trvE.join(",")+"\n") ;
// build the ordered sums
    var ordsumE = devloop( nE,trvE ) ;
    res += ("the 2^n sums for the function input:\n\t"+ ordsumE.join(",").substr(0,40)+"...\n") ;

// and try to find trvE
    res += ( "return :\n\t"+main(ordsumE,nE).join(",")+"\n" ) ;
}
res = res + "\n" ;

salida de la señal

the list to find :
    1,2,3,6,12,14,26
the 2^n sums for the function input: 
    0,1,2,3,3,4,5,6,6,7,8,9,9,10,11,12,12,13...
return :
    1,2,3,6,12,14,26


the list to find :
    1,2,3,6,9,11,12,14,26
the 2^n sums for the function input:
    0,1,2,3,3,4,5,6,6,7,8,9,9,10,11,12,9,10,...
return :
    1,2,3,6,9,11,12,14,26


the list to find :
    1,2,2,6,8,10,10,12,13,14,26
the 2^n sums for the function input: 
    0,1,2,3,2,3,4,5,6,7,8,9,8,9,10,11,8,9,10...
return :
    1,2,2,6,8,10,10,12,13,14,26


the list to find :
    1,1,2,2,2,6,8,10,10,10,13,14,126
the 2^n sums for the function input: 
    0,1,1,2,2,3,3,4,2,3,3,4,4,5,5,6,2,3,3,4,...
return :
    1,1,2,2,2,6,8,10,10,10,13,14,126