Escogiendo cinco números que suman S

Question

Dada una matriz A de N números no negativos, estoy interesado en encontrar la cantidad de formas en que puede elegir 5 números (desde distintas posiciones en la matriz) de manera que su suma sea S.

Hay una solución fácil en O(N^3):

Let H be a hash table of (sum, position of leftmost element of sum) 
for i = 0, N 
    for j = i + 1, N 
     H.add(A[i] + A[j], i) 

numPossibilities = 0 
for i = 0, N 
    for j = i + 1, N 
     for k = j + 1, N 
      numPossibilities += H.get(S - (A[i] + A[j] + A[k]), k) 

Dónde H.get(x, y) devuelve el número de elementos en el hash cuya suma tiene el mismo hash que x y cuyo elemento más a la izquierda es más grande que k.

Como alternativa, podemos agregar sumas de 3 elementos a la tabla hash y luego continuar con 2 bucles for anidados. Sin embargo, la complejidad sigue siendo la misma, y ​​solo usamos más memoria.

Suponiendo que las entradas serán bastante aleatorio (lo que no hay peor de los casos hash), ¿existe un algoritmo que puede resolver esto en O(N^2) o tal vez O(N^2 log N), o incluso O(N^3) si se mantiene en todos los casos? Estoy pensando que la búsqueda binaria podría ayudar, pero no veo cómo lidiar con índices superpuestos.

La solución anterior es mucho mejor en la práctica que la solución ingenua 5-for-loops, sin embargo, tengo la sensación de que podemos hacer mucho mejor, de ahí esta pregunta.

Si puede demostrar que no existe tal algoritmo, ¿cómo se puede optimizar la solución anterior?

Aclaración:

El algoritmo anterior es de hecho O(N^5) en el peor de los casos, por ejemplo cuando la matriz dada no contiene más que el número 1 y tenemos S = 5. En promedio, sin embargo, el método H.get está mucho más cerca de O(1), de ahí mi complejidad cúbica promedio.

Si implementa esto y lo ejecuta en 1000 números aleatorios en un intervalo grande (digamos 0 hasta Int32.MaxValue), verá que se ejecuta relativamente rápido. Aún así, no es difícil encontrar entradas para las cuales lleva mucho tiempo. Incluso si no podemos hacerlo funcionar lo suficientemente rápido para todos los números iguales, ¿qué optimizaciones podríamos hacer?

Bajo las mismas suposiciones, ¿podemos hacerlo mejor, de manera asintótica o al menos en la práctica?

Answer 1

Creo que el hecho de que los números deben tener posiciones distintas es una pista falsa. Puede usar el principio de inclusión-exclusión para contar el número de todas las posiciones (i, j, k, l, m) donde x [i] + x [j] + x [k] + x [l] + x [ m] = S y i, j, k, l, m son distintos:

sums with i!=j,i!=k,i!=l...,l!=m = all sums 
            - sums with i=j 
            - ... 
            - sums with l=m 
            + sums with i=j and j=k 
            + ... 
            + sums with k=l and l=m 
            - ... 
            + sums with i=j=k=l=m 

Cálculo de las cantidades a la derecha, excepto la primera, es factible en O (N^2 log N). Por ejemplo, para encontrar el número de posiciones (i, i, k, l, m) tales que x [i] + x [i] + x [k] + x [l] + x [m] = S usted puede crea matrices ordenadas con sumas {2a + b} y {c + d} y comprueba si tienen elementos x, y tales que x + y = S.

algoritmo principal

Así que es suficiente para calcular cuántos hay posiciones (i, j, k, l, m) donde x[i]+x[j]+x[k]+x[l]+x[m]=S y i, j, k, l, m no son necesariamente diferentes. Básicamente, se puede utilizar la solución de Morón de esta manera:

• crear una matriz ordenada de sumas {a + b: a, b son números de serie}; agrupe los elementos iguales en uno, recordando el recuento. Por ejemplo, para la matriz [1,1,3] se obtienen nueve sumas [2,2,2,2,4,4,4,4,6] de la forma a + b. Luego, agrupa los mismos elementos que recuerdan los recuentos: [(2,4), (4,4), (6,1)]. Este paso es O (N^2 log N).

• Para cada e, cuente cuántos hay pares de elementos en la matriz que suman a S-e. Como en la solución de Moron, tienes dos indicadores, uno va a la derecha, uno va a la izquierda. Si la suma es demasiado baja, mueva el primer puntero aumentando la suma; si la suma es demasiado alta, mueva el segundo puntero disminuyéndola.

  Supongamos que la suma es correcta. Esto significa que uno apunta a (a, x) y al segundo a (b, y) donde a + b = S-e. Aumente el contador en x * y y mueva ambos punteros (podría mover solo un puntero, pero en el siguiente paso no habría coincidencia, y el segundo puntero se movería en ese momento).

Por ejemplo, para [(2,4), (4,4), (6,1)] matriz y Se = 8, los puntos primero puntero en (2,4) y el segundo en (6,1) Como 2 + 6 = 8, agrega 4 y mueve ambos punteros. Ahora ambos apuntan a (4,4), por lo que aumenta el contador por 16. ¡No se detengan! Los punteros se superan, y se obtiene primero en (6,1), segundo en (2,4), aumenta el contador en 4.

Entonces, al final, hay 4 + 16 + 4 = 24 8 maneras de conseguir como una suma de 4 elementos de [1,1,3]:

>>> len([k for k in itertools.product([1,1,3],repeat=4) if sum(k) == 8]) 
24 

Prelude Control.Monad> length [k | k <- replicateM 4 [1,1,3], sum k == 8] 
24 

repetir que para cada correo, obtendrá el recuento de maneras de conseguir S como una suma de 5 elementos.

Para [1,1,1,1,1] y Se = 4, la matriz de sumas sería [(2,25)], y obtendría que hay 625 formas de obtener la suma de 4.

Para cada e, este paso es lineal en tamaño de la matriz (por lo que es O (N)), por lo que el bucle de toma O (N).

En inclusión-exclusión:

Call un quíntuple (i, j, k, l, m) "adecuado" si x [i] + x [j] + x [k] + x [ l] + x [m] = S. El objetivo es contar el número de quíntuples adecuados (i, j, k, l, m) donde i, j, k, l, m son distintos por pares. El algoritmo principal puede contar en O (N^3) cuántos hay quíntuples adecuados que no tienen necesariamente componentes distintos. Lo que resta es contar esas tuplas "incorrectas".

Considere los subconjuntos de adecuada quintuplica

A _xy = {(i, j, k, l, m): índices en x-ésimo y y-º lugar son los mismos}

Por ejemplo, A es el conjunto de quintuplica adecuado (i, j, k, l, m), donde j = l.

El conjunto de mal quintuplica es:

Un ∪ A ∪ ... ∪ A

Contando su cardinalidad de inclusión-exclusión:

| Un ∪ A ∪ ... ∪ A | = | A | + | A | + ... + | A | - | A ∩ A | - ... - | A ∩ A | + ... + | A ∩ A ... ∩ ∩ A ∩ A |

Hay 2 = 1024 sumideres aquí. Pero muchas de las cardinalidades son iguales.

Las únicas cosas que hay que contar es:

• X = | A | - quintuplica con i = j
• X = | A ∩ A | - quíntuples con i = j = k
• X = | A ∩ A ∩ A | - quíntuples con i = j = k = l
• X = | A ∩ A ∩ A ∩ A | - quíntuples con i = j = k = l = m
• X = | A ∩ A | - quíntuples con i = j, k = l
• X = | A ∩ A ∩ A | - quíntuples con i = j = k, l = m

Puede observar que, al permutar, todos los demás juegos se representan aquí. Por ejemplo, A tiene la misma cardinalidad que A .

Counting cardinalidades de esos 6 juegos es bastante fácil. Para el primero, crea arrays {2a + b} y {c + d} y cuenta cuántos hay elementos comunes; para los demás, solo hay 3 o menos variables libres, por lo que incluso un simple bucle le dará O (N^3).

Para simplificar la suma, escribí el siguiente programa Haskell:

import Control.Monad 
import Data.List 
import qualified Data.Map as Map 

-- Take equivalence relation, like [(1,2),(2,3)] and return its partition, like [3,1,1] 
f xs = sort $ map length $ foldr f (map return [1..5]) xs 
     where f (x,y) a = let [v1] = filter (x `elem`) a 
          [v2] = filter (y `elem`) a 
         in if v1 == v2 then a else (a \\ [v1,v2]) ++ [v1++v2] 

-- All 1024 subsets of [(1,2),(1,3), ..., (4,5)] 
subsets = filterM (const [False, True]) [(i,j) | i <- [1..5], j <- [i+1..5]] 

res = Map.fromListWith (+) $ map (\k -> (f k, (-1)^(length k))) subsets 

*Main> res 
Loading package array-0.3.0.1 ... linking ... done. 
Loading package containers-0.3.0.0 ... linking ... done. 
fromList [([1,1,1,1,1],1),([1,1,1,2],-10),([1,1,3],20),([1,2,2],15),([1,4],-30),([2,3],-20),([5],24)] 

lo que significa que la fórmula es

todos los subconjuntos - 10X + 20X - 30X + 24X + 15X - 20X .

Comprobar:

¿Cuántos hay en quintuplica [0,0,0, ..., 0] que suman 0?Una forma de calcular que es directamente, segunda forma es utilizar la fórmula (y no se preocupan por posiciones distintas):

direct x = x*(x-1)*(x-2)*(x-3)*(x-4) 
indirect x = x^5 - 10 * x^4 + 20 * x^3 + 15 * x^3 - 30 * x^2 - 20*x^2 + 24*x 

*Main> direct 100 
9034502400 
*Main> indirect 100 
9034502400 

Otras observaciones:

Además, hay O (un registro _n un _n) solución: Compute (x ^un + ... + x ^{un _n}) usando FFT, el resultado es el coeficiente en x ^S. Esto permite una cierta _i para ser utilizado dos veces, pero se puede restar polinomios como (x ^2a + ... + x ^{2a _n}) * (x ^un + ... + x ^{a _n}) etc. de acuerdo con el principio de inclusión-exclusión.

En algunos modelos de computación restringidos, ha sido shown la versión de decisión de este problema requiere O (N^3) tiempo.

Answer 2

Puede hacerlo en O (N * S) con la programación dinámica:

static int count(int[] A, int S) { 
    final int K = 5; 
    // In count[n][s] we'll count the number of ways you can pick n numbers such that their sum is s 
    int[][] count = new int[K+1][S+1]; 

    count[0][0] = 1; // The base case 
    for (int i = 0; i < A.length; i++) 
     for (int n = K; n >= 1; n--) 
      for (int s = A[i]; s <= S; s++) 
       count[n][s] += count[n-1][s - A[i]]; 

    return count[K][S]; 
} 

Answer 3

O (n^3) parece posible (aunque no he intentado demostrarlo).

Tome todos los pares posibles y cree una nueva matriz (digamos B) de tamaño O (N^2) que contiene la suma de todos los pares posibles. También realice un seguimiento del índice de dos elementos del conjunto original que dio esa suma. - O (N^2)

Ahora ordena la matriz - O (N^2LogN).

Ahora, para cada elemento a en la matriz original, intente encontrar dos elementos de B que suman a S-a. Como B se clasifica, esto se puede hacer en el tiempo O (B): comience con dos punteros, uno al máximo y uno al mínimo.

Si suma de esos dos> S-a, disminuya el puntero cerca del máx.

Si suma de esos dos < S-a, incremente el puntero cerca de min.

Si la suma es igual, ha encontrado un par de candidatos y una nueva sub-matriz ordenada en la que buscar el siguiente posible par de candidatos. (Debe asegurarse de que los dos elementos de B provienen de cuatro elementos de A). (Puede haber problemas potenciales aquí)

Así puede contar el número de veces que S-a ocurre como una suma de dos elementos de B, que provienen de cuatro elementos del conjunto original (sin incluir a).

Entonces O (N^2) tiempo para O (N) elementos - O (N^3).

Espero que ayude.

Answer 4

Quizás sea mejor crear primero una matriz con solo valores distintos y contar la ocurrencia de ellos en la matriz original. Debido a que solo se desea la cantidad de soluciones y no las soluciones en sí, eso podría ser más rápido si se usan cálculos combinados.

1) Ordenar array A O (N log N)

2) Crea una nueva matriz B donde todos los valores son distintos. Guarde también el recuento de la aparición del valor en la matriz original A para cada elemento en B. O (N)

3) Cree una nueva matriz C con sumas de dos elementos de B. Incluyendo sumas del mismo elemento si el conteo> 1. Guarde también ambos índices de los elementos de B. O (| B |)

4) Clasificar array C por el O sumas (| B | (log | B |))

5) Para todos los elementos de B encuentre dos elementos válidos de C de modo que los tres valores se suman a S y los índices estén en el mismo orden. En pseudocódigo:

num=0 
for (i=0; i<n; i++) 
    j=i 
    k=|C|-1 
    while (j <= k) 
    if (c[j].sum + c[k].sum = S - b[i].value) 
     for (m=0; m<c[j].index.length; m++) 
     for (n=0; n<c[k].index.length; n++) 
      if (i < c[j].index[m].left < c[j].index[m].right < c[j].index[k].left < c[j].index[k].right) 
      num+=b[i].count * b[c[j].index[m].left].count * b[c[j].index[m].right].count * b[c[j].index[k].left].count * b[c[j].index[k].right].count 
      else if (b[i].count > 1 && i = c[j].index[m].left < c[j].index[m].right < c[j].index[k].left < c[j].index[k].right) 
      num+= binomialcoefficient(b[i].count, 2) * b[c[j].index[m].right].count * b[c[j].index[k].left].count * b[c[j].index[k].right].count 
      else if (b[c[j].index[m].left].count > 1 && i < c[j].index[m].left = c[j].index[m].right < c[j].index[k].left < c[j].index[k].right) 
      num+= b[i].count * binomialcoefficient(b[c[j].index[m].left].count, 2) * b[c[j].index[k].left].count * b[c[j].index[k].right].count 
      [..] 
      else if (b[i].count > 2 && i = c[j].index[m].left = c[j].index[m].right < c[j].index[k].left < c[j].index[k].right) 
      num+= binomialcoefficient(b[i].count, 3) * b[c[j].index[k].left].count * b[c[j].index[k].right].count 
      [..] 
      else if (b[i].count > 1 && b[c[j].index[m].right].count > 1 && i = c[j].index[m].left < c[j].index[m].right = c[j].index[k].left < c[j].index[k].right) 
      num+= binomialcoefficient(b[i].count, 2) * binomialcoefficient(b[c[j].index[m].right].count, 2) * b[c[j].index[k].right].count 
      [..] 
      else if (b[i].count > 4 && i = c[j].index[m].left = c[j].index[m].right = c[j].index[k].left = c[j].index[k].right) 
      num+= binomialcoefficient(b[i].count, 5) 
    if (c[j].sum + c[k].sum >= S - b[i].value) 
     k-- 
    if (c[j].sum + c[k].sum <= S - b[i].value) 
     j++ 

No estoy realmente seguro de lo que el tiempo la complejidad que tenga. El bucle for externo está vinculado por O (| B |), el bucle while por O (| B |), el interno por bucles por O (| B |), porque B tiene solo valores distintos. Tan obvisouly está en O (| B |). Pero es O (N) si todos los elementos en A tienen el mismo valor y si todos los valores son distintos y suficientemente aleatorios, es posible vincular el número de índices por suma en C por una constante, lo que llevaría a O (N).

El peor de los casos podría ser en algún lugar con la mitad de los valores iguales y la otra mitad al azar o con todos los números distintos pero con muchas sumas duplicadas. Pero eso también llevaría a un ciclo mucho más corto. Tengo la sensación de que el tiempo y los dos bucles For internos están obligados por O (N), entonces O (N) en total para todos los casos, pero no puedo probarlo.

También una pregunta interesante aquí es cuál es el número máximo de posibilidades para recoger 5 números que suman S para una matriz de N números de disctinct. Si está en O (N), el peor caso de ese algoritmo es también O (N).

Quizás probarlo;).