Dado un conjunto múltiple de números naturales X, considere el conjunto de todas las sumas posibles:

$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$

Por ejemplo, $\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$ mientras que $\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$ .

¿Cuál es el algoritmo más eficiente para calcular la operación inversa (medido en términos del tamaño del conjunto de sumas de entrada)? Específicamente, es posible calcular eficientemente cualquiera de los siguientes:

1. Si un conjunto dado es un conjunto válido de sumas. (Por ejemplo, $\left\{0,1,2\right\}$ es válido pero $\left\{0,1,3\right\}$ no lo es).
2. Un conjunto múltiple que suma al conjunto dado.
3. El multiset más pequeño que se suma al conjunto dado. (Por ejemplo, $\left\{1,2\right\}$ y $\left\{1,1,1\right\}$ ambos suman $\left\{0,1,2,3\right\}$ pero el primero es más pequeño).

Solución

La solución tiene dos partes. Primero descubrimos un conjunto mínimo, luego demostramos que puede representar el conjunto de suma de potencia. La solución se ajusta para la implementación de la programación.

Algoritmo de conjunto mínimo

1. Encuentre el elemento máximo del conjunto de suma (múltiple). P , el conjunto mínimo potencial (múltiple) está inicialmente vacío.$a_{m}$$P$

2. A menos que haya sólo un grupo, representan en todas las formas posibles como un par de sumas que se suman a una m , S i j = { ( a i , un j ) | a i + a j = a m$a_{m}$$a_{m}$$S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$

3. Compruebe que todos los elementos del conjunto de sumas estén incluidos.

4. Encuentre el elemento máximo de todos los S i j (que significan juntos) con la siguiente propiedad: para cada S i j , a s está en S i j , o podemos encontrar una p del conjunto de sumas para que a p + a s está en S i j .$a_{s}$$S_{ij}$$S_{ij}$$a_{s}$$S_{ij}$$a_{p}$$a_{p}+a_{s}$$S_{ij}$

5. Si es el caso de que no contiene una s , solo la suma a s + a p , elimine a p + a s de S i j (o simplemente establezca una marca para ignorarlo) e inserte una p y una s en S i j en su lugar.$S_{ij}$$a_{s}$$a_{s}+a_{p}$$a_{p}+a_{s}$$S_{ij}$$a_{p}$$a_{s}$$S_{ij}$

6. Si un elemento está presente en cada eliminarlo de todo S i j una vez (o acaba de establecer una marca de ignorarlo y no tocar por más tiempo) y añadirlo a la lista de elementos de potencial conjunto mínimo P .$S_{ij}$$S_{ij}$$P$

7. Repita hasta que todos estén vacíos$S_{ij}$

8. Si algo de permanece no vacío y no podemos continuar, intente nuevamente con el valor máximo de todos S i j .$S_{ij}$$S_{ij}$

9. Recrear los pasos recursivos sin el traslado y continuar con el algoritmo de cobertura de conjunto potencia sobre . (Antes de esto, puede hacer una comprobación segura de que P incluye todos los elementos que no pueden representarse como una suma de dos elementos, por lo que deben estar en el conjunto subyacente con seguridad. Por ejemplo, el elemento mínimo debe estar en P ).$P$$P$$P$

(10. Observe que una solución de conjunto mínima que es el objetivo del algoritmo no puede contener más de una repetición del mismo número).

Ejemplo:

$$\{2,3,5,7,8,10,12,13,15\}$$

Representa 15 en todas las formas posibles como una suma de dos números del conjunto de sumas.

$$(13,2),(12,3),(10,5),(8,7)$$

Trate de encontrar el número máximo que está en todos los grupos o que puede representarse como una suma. Obviamente podemos comenzar a buscarlo desde 8, no tiene sentido ir por encima de él.

13 del primer grupo es 13 = 8 + 5, por lo que 13 está bien, pero 12 del segundo grupo no está bien ya que no hay 4 para hacer 12 = 8 + 4 en el conjunto de sumas. Luego intentamos con 7. Pero inmediatamente 13 no puede ser cubierto, no hay 6.

Luego intentamos 5. 13 = 5 + 8, 12 = 5 + 7, 10 = 5 + 5, y para el último 8 = 5 + 3 o 7 = 5 + 2 pero no ambos. Los grupos son ahora:

$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$

5 se repite en todos los grupos, por lo que lo extraemos . Extraemos 5 solo una vez de cada grupo.$P=\{5\}$

$$(8,2),(7,3),(5,5),(3,7)$$

Obviamente no tiene sentido ir más allá de 5, así que intentamos 5 nuevamente. 8 = 5 + 3, 7 = 5 + 2, entonces todo está bien

$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$

Extraiga un 5 nuevamente de todos los grupos ya que se está repitiendo. (Esto no es común, pero nuestro caso se crea deliberadamente para mostrar qué hacer en caso de que tengamos repeticiones). $P=\{5,5\}$

$$(3,2),(2,3),(5),(3,2)$$

Ahora intentamos con 3 y tenemos 5 = 3 + 2. Agréguelo al grupo.

$$(3,2),(2,3),(3,2),(3,2)$$

Ahora extraiga 3 y 2 ya que se repiten en todas partes y estamos bien y los grupos están vacíos.$P=\{5,5,3,2\}$

$$(),(),(),()$$

Ahora, necesitamos recrear pasos recursivos sin eliminaciones, esto simplemente significa hacer lo anterior sin eliminar realmente los elementos de simplemente colocándolos en P y marcando para no alterarlos más.$S_{ij}$$P$

( ( 5 , 8 ) , 2 ) , ( ( 5 , 7 ) , 3 ) , ( ( 5 , 5 ) , 5 ) , ( ( 5 , 3 ) ,

$$(13,2),(12,3),(10,5),(8,7)$$ ( ( 5 , ( 5 , 3 ) ) , 2 ) , ( ( 5 , ( 5 , 2 ) ) , 3 ) , ( ( 5 , ( 3 , 2 ) ) , 5 ) , ( ( 5 , 3 ) , ( 5 , 2 ) $$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$ $$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

Cobertura de potencia establecida

El propósito de esta parte es verificar si el conjunto mínimo encontrado puede cubrir el conjunto de suma de potencia. Es posible que una solución encontrada pueda cubrir todas las sumas dadas, pero que no sean sumas de potencia establecida. (Técnicamente, podría simplemente crear un conjunto de suma de potencia a partir del conjunto mínimo encontrado y verificar si cada suma, como lo establece el conjunto de potencia, está en el conjunto de suma inicial. Esto es todo lo que se fusionó con lo que ya tenemos, por lo que no se desperdicia nada Puede hacer esta parte mientras rebobina la recursión).

1. Codifique todos los elementos del conjunto mínimo utilizando potencias sucesivas de 2. El orden no es importante. Codifique el mismo elemento con un nuevo valor tantas veces como se repita. Comience desde C = 1, cada elemento siguiente tiene C = 2C.

$$(2=[1],3=[2],5=[4],5=[8])$$

2. Reemplace los elementos en la lista de recursión restaurada,

$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

con la codificación: 2 con 1, 3 con 2, 5 con 4 y otros 5 con 8. Observe que cada elemento tiene una codificación diferente aunque se repitan.

$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$

3. Recoge todas las sumas intermedias, en este momento tenemos (1,2,4,8)

$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$

$(1,2,3,4,5,8,9,10)$

$$((14),1),((13),2),((7),8),(15)$$

$(1,2,3,4,5,8,9,10,13,14,15)$

$$\{(15),(15),(15),(15)\}$$

4. $2^m-1$$m$$m=4$

5. $1$$2^m-1$

$(6,7,11,12)$

6. Justifique su ausencia de la siguiente manera: represente cada número en forma binaria

$(6=0110_2)$ $(7=0111_2)$ $(11=1011_2)$ $(12=1010_2)$

$6$$0110_2$$(2=[1],3=[2],5=[4],5=[8])$$\{2,3,5,7,8,10,12,13,15\}$Así que todo está bien.

$7$$0111_2$$(2=[1],3=[2],5=[4],5=[8])$

$11$$12$

Si alguna representación binaria corresponde a la suma que no se puede encontrar, informe que no hay solución.

$(2,3,5,5)$

Discusión

Era necesario proporcionar el algoritmo que verificará si las sumas cubren la finalización del conjunto de potencia, que es lo que está oculto en la expansión binaria. Por ejemplo, si excluimos 8 y 7 del ejemplo inicial, la primera parte aún proporcionaría la solución, solo la segunda parte informaría las combinaciones faltantes de sumas.

$mnlog(m)$$m\log^2(m)$$m$$n$$\log(m)$

$m$$\log{m}$$m\log^2(m)$

$m\log^3(m)$

Partes del algoritmo suponen que podemos encontrar el par de sumas en tiempo lineal y esto requiere una clasificación.

Inicio incorrecto

$2,3,4,5,6,7,8,9,10,11,12,13,15$$2,3,4,6$$S_{ij}$

$5,4,3,3$

$2,2,3,4,4$$2,3,4,6$

El propósito de este algoritmo es proporcionar una solución una vez que hayamos comenzado todo correctamente.

Mejoras

El paso 4. es el que podría actualizarse de esta manera: en lugar de la máxima, podríamos probar cada elemento en orden descendente que satisfaga la condición dada. Creamos una rama separada para cada uno. Si alguna rama no da una solución, cancélela.

$2,3,4,5,6,7,8,9,10,11,12,13,15$$7,6,5,4$de manera separada ya que todos pasan la primera prueba. (No hay ninguna razón para usar 2 o 3, ya que sabemos que tienen que estar en el conjunto subyacente) y simplemente continuar de esa manera hasta que recopilemos todas las versiones que puedan llegar al final. Esto crearía una solución de cobertura total que descubriría más de un conjunto subyacente.

Otra cosa, ya que sabemos que no podemos tener más de una repetición si el caso es mínimo, podemos incorporar esto en nuestro algoritmo.

En general, la condición en el paso 4. de que un número debe repetirse en cada grupo o tener la capacidad de crear una suma es lo suficientemente fuerte como para sacarnos de las aguas exponenciales directas, lo que sería un algoritmo de simplemente probar cada combinación y crear la potencia establecer sobre cada uno hasta que encontremos una coincidencia.

NOTA: Esto no funciona del todo en general, consulte el contraejemplo de Uri a continuación.

$Y$$Y$

• $0\in Y$
• $y$$Y$$y$$X$$Y$
• $z_1<\dots<z_n$$Y$$Y'$$Y = Y' + \{0,y\}$$0$$Y'$$i=1,\dots,n$$z_i+y\in Y$$z_i$$Y'$$z_i-y\notin Y$$z_i+y\notin Y$$z_i+y\in Y$$z_i$$Y'$
• $Y'$$y,y',\dots$

$1$$y$$O(n)$$O(n^2)$

$Y=\{0,1,3,4,5,6,7\}$$\{0,1,3,4,6\}$$\{0,1,3,5,6\}$$y\in Y$$\{a+k\cdot y\}$$Y$$Y'$