Dados los nnúmeros en una matriz (no se puede suponer que son enteros), me gustaría calcular el producto de todos los subconjuntos de tamaño n-1.

Puede hacerlo multiplicando todos los números y luego dividiéndolos por turnos, siempre que ninguno de los números sea cero. Sin embargo, ¿qué tan rápido puedes hacer esto sin división?

Si no permite la división, ¿cuál es el número mínimo de operaciones aritméticas (por ejemplo, multiplicación y suma) necesarias para calcular el producto de todos los subconjuntos de tamaño n-1?

Claramente puedes hacerlo en (n-1)*nmultiplicaciones.

Para aclarar, la salida son nproductos diferentes y las únicas operaciones aparte de leer y escribir en la memoria permitidas son la multiplicación, la suma y la resta.

Ejemplo

Si la entrada tiene tres números 2,3,5, entonces la salida es tres números 15 = 3*5, 10 = 2*5y 6 = 2*3.

Criterio ganador

Las respuestas deben dar una fórmula exacta para la cantidad de operaciones aritméticas que usará su código en términos de n. Para simplificar la vida, simplemente conectaré n = 1000tu fórmula para juzgar su puntaje. Cuanto más bajo, mejor.

Si es demasiado difícil producir una fórmula exacta para su código, puede ejecutarla n = 1000y contar las operaciones aritméticas en el código. Sin embargo, una fórmula exacta sería la mejor.

Debe agregar su puntaje n=1000a su respuesta para una comparación fácil.

Python, 3 (n-2) operaciones, puntaje = 2994

l = list(map(float, input().split()))
n = len(l)

left = [0] * len(l)
right = [0] * len(l)
left[0] = l[0]
right[-1] = l[-1]
for i in range(1,len(l)-1):
  left[i] = l[i] * left[i - 1]
  right[-i-1] = l[-i-1] * right[-i]

result = [0] * len(l)
result[-1] = left[-2]
result[0] = right[1]
for i in range(1, len(l) - 1):
  result[i] = left[i - 1] * right[i+1]

print(result)

Las matrices lefty rightcontienen los productos acumulados de la matriz desde la izquierda y desde la derecha, respectivamente.

EDITAR: Prueba de que 3 (n-2) es el número óptimo de operaciones necesarias para n> = 2, si solo usamos la multiplicación.

Lo haremos por inducción; según el algoritmo anterior, solo tenemos que demostrar que para n> = 2, 3 (n-2) es un límite inferior en el número de multiplicaciones necesarias.

Para n = 2, necesitamos al menos 0 = 3 (2-2) multiplicaciones, por lo que el resultado es trivial.

Supongamos que n> 2, y supongamos que para n - 1 elementos, necesitamos al menos 3 (n-3) multiplicaciones. Considere una solución para n elementos con k multiplicaciones. Ahora, eliminamos el último de estos elementos como si fuera 1, y simplificamos todas las multiplicaciones directamente por él. También eliminamos la multiplicación que conduce al producto de todos los demás elementos, ya que ese no es necesario, ya que nunca se puede utilizar como un valor intermedio para obtener el producto de n-2 de los otros elementos, ya que la división no está permitida. Esto nos deja con l multiplicaciones, y una solución para n - 1 elementos.

Por hipótesis de inducción, tenemos l> = 3 (n-3).

Ahora, echemos un vistazo a cuántas multiplicaciones se eliminaron. Uno de ellos fue el que condujo al producto de todos los elementos, excepto el último. Además, el último elemento se usó directamente en al menos dos multiplicaciones: si se usó en una sola, se usó al multiplicar por un resultado intermedio que consiste en algún producto de los otros elementos; digamos, sin pérdida de generalidad, este resultado intermedio incluye el primer elemento en el producto. Entonces, no hay forma de obtener el producto de todos los elementos, excepto el primero, ya que cada producto que contiene el último elemento es el último o contiene el primer elemento.

Por lo tanto, tenemos k> = l + 3> = 3 (n-2), lo que demuestra el teorema reivindicado.

Haskell , puntuación 2994

group :: Num a => [a] -> [[a]]
group (a:b:t) = [a,b] : group t
group [a] = [[a]]
group [] = []

(%) :: (Num a, Eq a) => a -> a -> a
a % 1 = a
1 % b = b
a % b = a * b

prod_one_or_two :: (Num a, Eq a) => [a] -> a
prod_one_or_two [a, b] = a % b
prod_one_or_two [x] = x

insert_new_value :: (Num a, Eq a) => ([a], a) -> [a]
insert_new_value ([a, b], c) = [c % b, c % a]
insert_new_value ([x], c) = [c]

products_but_one :: (Num a, Eq a) => [a] -> [a]
products_but_one [a] = [1]
products_but_one l = 
    do combination <- combinations ; insert_new_value combination
    where 
        pairs = group l
        subresults = products_but_one $ map prod_one_or_two pairs
        combinations = zip pairs subresults

Pruébalo en línea!

Digamos que nos dan la lista [a,b,c,d,e,f,g,h]. Primero lo agrupamos en pares [[a,b],[c,d],[e,f],[g,h]]. Luego, recurrimos a la lista pairsde tamaño medio de sus productos para obtenersubresults

[a*b, c*d, e*f, g*h] -> [(c*d)*(e*f)*(g*h), (a*b)*(e*f)*(g*h), (a*b)*(c*d)*(g*h), (a*b)*(c*d)*(e*f)]

Si tomamos el primer elemento (c*d)*(e*f)*(g*h)y lo multiplicamos por by arespectivamente, obtenemos el producto de todo pero ay todo menos b. Al hacer esto para cada par y resultado recursivo con ese par perdido, obtenemos el resultado final. El caso de longitud impar se maneja especialmente haciendo pasar el elemento impar sin emparejar al paso recursivo, y el producto de los elementos restantes devueltos es el producto sin él.

El número de multiplicaciones t(n)es n/2para el producto de emparejamiento, t(n/2)para la llamada recursiva y otro npara los productos con elementos individuales. Esto da t(n) = 1.5 * n + t(n/2)por extraño n. El uso de recuentos más precisos para la nmultiplicación impar e ignorando 1para el caso base da puntaje 2997para n=1000.

Haskell , puntaje 9974

partition :: [Float] -> ([Float], [Float])
partition = foldr (\a (l1,l2) -> (l2, a:l1)) ([],[])

(%) :: Float -> Float -> Float
a % 1 = a
1 % b = b
a % b = a*b

merge :: (Float, [Float]) -> (Float, [Float]) -> (Float, [Float])
merge (p1,r1) (p2, r2) = (p1%p2, map(%p1)r2 ++ map(%p2)r1)

missing_products' :: [Float] -> (Float, [Float])
missing_products' [a] = (a,[1])
missing_products' l = merge res1 res2
    where
        (l1, l2) = partition l
        res1 = missing_products' l1
        res2 = missing_products' l2

missing_products :: [Float] -> [Float]
missing_products = snd . missing_products'

Pruébalo en línea!

Una estrategia de divide y vencerás, que recuerda mucho al tipo de fusión. No hace ninguna indexación.

La función partitiondivide la lista en mitades tan iguales como sea posible al colocar elementos alternos en lados opuestos de la partición. Fusionamos recursivamente los resultados (p,r)para cada una de las mitades, con rla lista de productos con uno perdido y pel producto general.

Para la salida de la lista completa, el elemento que falta debe estar en una de las mitades. El producto que falta ese elemento es un producto que falta para la mitad en el que está, multiplicado por el producto completo para la otra mitad. Entonces, multiplicamos cada producto con uno perdido por el producto completo de la otra mitad y hacemos una lista de los resultados, comomap(*p1)r2 ++ map(*p2)r1) . Esto toma nmultiplicaciones, donde nes la longitud. También tenemos que hacer un nuevo producto completo p1*p2para uso futuro, que cuesta 1 multiplicación más.

Esto le da a la recursión general para el número de operaciones t(n)con naún: t(n) = n + 1 + 2 * t(n/2). El impar es similar, pero una de las sublistas es 1más grande. Al hacer la recursión, obtenemos n*(log_2(n) + 1)multiplicaciones, aunque la distinción par / impar afecta ese valor exacto. Los valores hasta t(3)se mejoran al no multiplicar por1 definiendo una variante (%)de los (*)accesos directos a los casos _*1o 1*_.

Esto da 9975multiplicaciones para n=1000. Creo que la pereza de Haskell significa que no se calcula el producto general no utilizado en la capa externa 9974; si me equivoco, podría omitirlo explícitamente.

Haskell , puntuación 2994

group :: [a] -> Either [(a, a)] (a, [(a, a)])
group [] = Left []
group (a : l) = case group l of
  Left pairs -> Right (a, pairs)
  Right (b, pairs) -> Left ((a, b) : pairs)

products_but_one :: Num a => [a] -> [a]
products_but_one [_] = [1]
products_but_one [a, b] = [b, a]
products_but_one l = case group l of
  Left pairs ->
    let subresults =
          products_but_one [a * b | (a, b) <- pairs]
    in do ((a, b), c) <- zip pairs subresults; [c * b, c * a]
  Right (extra, pairs) ->
    let subresult : subresults =
          products_but_one (extra : [a * b | (a, b) <- pairs])
    in subresult : do ((a, b), c) <- zip pairs subresults; [c * b, c * a]

Pruébalo en línea!

Cómo funciona

Esta es una versión limpia del algoritmo de xnor que trata el caso extraño de una manera más directa (editar: parece que xnor lo ha limpiado de la misma manera):

[a, b, c, d, e, f, g] ↦
[a, bc, de, fg] ↦
[(bc) (de) (fg), a (de) (fg), a (bc) ( fg), a (bc) (de)] por recursión ↦
[(bc) (de) (fg), a (de) (fg) c, a (de) (fg) b, a (bc) (fg) e, a (bc) (fg) d, a (bc) (de) g, a (bc) (de) f]

[a, b, c, d, e, f, g, h] ↦
[ab, cd, ef, gh] ↦
[(cd) (ef) (gh), (ab) (ef) (gh), ( ab) (cd) (gh), (ab) (cd) (ef)] por recursión ↦
[(cd) (ef) (gh) b, (cd) (ef) (gh) a, (ab) (ef ) (gh) d, (ab) (ef) (gh) c, (ab) (cd) (gh) f, (ab) (cd) (gh) e, (ab) (cd) (ef) h, (ab) (cd) (ef) g].

O (n log n) operaciones, puntaje = 9974

Funciona con un árbol binario.

Pitón

l = list(map(int, input().split()))
n = len(l)

p = [0] * n + l
for i in range(n - 1, 1, -1):
  p[i] = p[i + i] * p[i + i+1]

def mul(x, y):
  if y == None:
    return x
  return x * y

r = [None] * n + [[None]] * n
for i in range(n - 1, 0, -1):
  r[i] = [mul(p[i + i + 1], x) for x in r[i + i]] + [mul(p[i + i], x) for x in r[i + i + 1]]

u = r[1]
j = 1
while j <= n:
  j += j
print(u[n+n-j:] + u[:n+n-j])

Esto también requiere operaciones de suma de listas y algo de aritmética en números que no son los valores de entrada; No estoy seguro si eso cuenta. La mulfunción está ahí para guardar n operaciones para el caso base, para evitar desperdiciarlas multiplicando por 1. En cualquier caso, se trata de operaciones O (n log n). La fórmula exacta es, si solamente contando operaciones aritméticas sobre números de entrada, con j = floor(log_2(n)): j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2.

¡Gracias a @xnor por guardar una operación con la idea de no calcular el producto externo!

La última parte es generar los productos en el orden del término faltante.

O ((n-2) * n) = O (n ² ): solución trivial

Esta es solo la solución trivial que multiplica cada uno de los subconjuntos:

Pitón

def product(array): # Requires len(array) - 1 multiplication operations
    if not array: return 1
    result = array[0]
    for value in array[1:]:
        result *= value
    return result

def getSubsetProducts(array):
    products = []
    for index in range(len(array)): # calls product len(array) times, each time calling on an array of size len(array) - 1, which means len(array) - 2 multiplication operations called len(array) times
        products.append(product(array[:index] + array[index + 1:]))
    return products

Tenga en cuenta que esto también requiere noperaciones de adición de lista; No estoy seguro si eso cuenta. Si eso no está permitido, product(array[:index] + array[index + 1:])puede reemplazarse por product(array[:index]) * product(array[index + 1:]), lo que cambia la fórmula a O((n-1)*n).

Python, 7540

Una estrategia de fusión tripartita. Creo que puedo hacerlo incluso mejor que esto, con una fusión aún grande. Es O (n log n).

EDITAR: se corrigió un error.

count = 0
def prod(a, b):
    if a == 1: return b
    if b == 1: return a
    global count
    count += 1
    return a * b

def tri_merge(subs1, subs2, subs3):
    total1, missing1 = subs1
    total2, missing2 = subs2
    total3, missing3 = subs3

    prod12 = prod(total1, total2)
    prod13 = prod(total1, total3)
    prod23 = prod(total2, total3)

    new_missing1 = [prod(m1, prod23) for m1 in missing1]
    new_missing2 = [prod(m2, prod13) for m2 in missing2]
    new_missing3 = [prod(m3, prod12) for m3 in missing3]

    return prod(prod12, total3), new_missing1 + new_missing2 + new_missing3

def tri_partition(nums):
    split_size = len(nums) // 3
    a = nums[:split_size]
    second_split_length = split_size + (len(nums) % 3 == 2)
    b = nums[split_size:split_size + second_split_length]
    c = nums[split_size + second_split_length:]
    return a, b, c

def missing_products(nums):
    if len(nums) == 1: return nums[0], [1]
    if len(nums) == 0: return 1, []
    subs = [missing_products(part) for part in tri_partition(nums)]
    return tri_merge(*subs)

def verify(nums, res):
    actual_product = 1
    for num in nums:
        actual_product *= num
    actual_missing = [actual_product // num for num in nums]
    return actual_missing == res[1] and actual_product == res[0]

nums = range(2, int(input()) + 2)
res = missing_products(nums)

print("Verified?", verify(nums, res))
if max(res[1]) <= 10**10: print(res[1])

print(len(nums), count)

La función relevante es missing_products, que proporciona el producto general y todos los que tienen un elemento faltante.

dc, puntaje 2994

#!/usr/bin/dc -f

# How it works:
# The required products are
#
#   (b × c × d × e × ... × x × y × z)
# (a) × (c × d × e × ... × x × y × z)
# (a × b) × (d × e × ... × x × y × z)
# ...
# (a × b × c × d × e × ... × x) × (z)
# (a × b × c × d × e × ... × x × y)
#
# We calculate each parenthesised term by
# multiplying the one above (on the left) or below
# (on the right), for 2(n-2) calculations, followed
# by the n-2 non-parenthesised multiplications
# giving a total of 3(n-2) operations.

# Read input from stdin
?

# We will store input values into stack 'a' and
# accumulated product into stack 'b'.  Initialise
# stack b with the last value read.
sb

# Turnaround function at limit of recursion: print
# accumulated 'b' value (containing b..z above).
[Lbn[ ]nq]sG

# Recursive function - on the way in, we stack up
# 'a' values and multiply up the 'b' values.  On
# the way out, we multiply up the 'a' values and
# multiply each by the corresponding 'b' value.
[dSalb*Sb
z1=G
lFx
dLb*n[ ]n
La*]dsFx

# Do the last a*b multiplication
dLb*n[ ]n

# And we have one final 'a' value that doesn't have a
# corresponding 'b':
La*n

Supongo que la comparación de enteros z1=(que termina la recursión cuando alcanzamos el último valor) es libre. Esto es equivalente a los gustos de foreachen otros idiomas.

Manifestaciones

for i in '2 3 5' '2 3 5 7' '0 2 3 5' '0 0 1 2 3 4'
do printf '%s => ' "$i"; ./127147.dc <<<"$i"; echo
done
2 3 5 => 15 10 6
2 3 5 7 => 105 70 42 30
0 2 3 5 => 30 0 0 0
0 0 1 2 3 4 => 0 0 0 0 0 0

Una demostración con entradas grandes y pequeñas:

./127147.dc <<<'.0000000000000000000542101086242752217003726400434970855712890625 1 18446744073709551616'
18446744073709551616 1.0000000000000000000000000000000000000000000000000000000000000000 .0000000000000000000542101086242752217003726400434970855712890625

C ++, puntaje: 5990, O ([2NlogN] / 3)

Esta implementación utiliza una tabla de búsqueda de árbol binario. Mi primera implementación fue O (NlogN), pero una optimización de último minuto, que busca el producto de todos los elementos de la matriz menos un par, + 2 multiplicaciones salvaron el día. Creo que esto aún podría optimizarse un poco más, tal vez otro 16% ...

He dejado algunos rastros de depuración, solo porque es más fácil eliminarlos que reescribirlos :)

[Editar] la complejidad real se mide en O ([2NlogN] / 3) para 100. En realidad, es un poco peor que O (NlogN) para conjuntos pequeños, pero tiende a O ([NlogN] / 2) a medida que la matriz crece O muy grande (0.57.NlogN) para un conjunto de 1 millón de elementos.

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <random>
#include <cstdlib>

using DataType = long double;

using DataVector = std::vector<DataType>;

struct ProductTree
{
    std::vector<DataVector> tree_;
    size_t ops_{ 0 };

    ProductTree(const DataVector& v) : ProductTree(v.begin(), v.end()) {}
    ProductTree(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        Build(first, last);
    }

    void Build(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        tree_.emplace_back(DataVector(first, last));

        auto size = std::distance(first, last);
        for (auto n = size; n >= 2; n >>= 1)
        {
            first = tree_.back().begin();
            last = tree_.back().end();

            DataVector v;
            v.reserve(n);
            while (first != last) // steps in pairs
            {
                auto x = *(first++);
                if (first != last)
                {
                    ++ops_;
                    x *= *(first++); // could optimize this out,small gain
                }
                v.push_back(x);
            }
            tree_.emplace_back(v);
        }
    }

    // O(NlogN) implementation... 
    DataVector Prod()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            result[i] = ProductAtDepth(i, depth);
        }
        return result;
    }

    DataType ProductAtDepth(size_t index, size_t depth) 
    {
        if (depth == 0)
        {
            return ((index ^ 1) < tree_[depth].size())
                ? tree_[depth][index ^ 1]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth(index, depth - 1);
        }
        return ProductAtDepth(index, depth - 1);
    }    

    // O([3NlogN]/2) implementation... 
    DataVector Prod2()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)    // steps in pairs
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            auto x = ProductAtDepth2(i, depth);
            if (i + 1 < tree_[0].size())
            {
                ops_ += 2;
                result[i + 1] = tree_[0][i] * x;
                result[i] = tree_[0][i + 1] * x;
                ++i;
            }
            else
            {
                result[i] = x;
            }
        }
        return result;
    }

    DataType ProductAtDepth2(size_t index, size_t depth)
    {
        if (depth == 1)
        {
            index = (index >> 1) ^ 1;
            return (index < tree_[depth].size())
                ? tree_[depth][index]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth2(index, depth - 1);
        }
        return ProductAtDepth2(index, depth - 1);
    }

};


int main()
{
    //srand(time());

    DataVector data;
    for (int i = 0; i < 1000; ++i)
    {
        auto x = rand() & 0x3;          // avoiding overflow and zero vaolues for testing
        data.push_back((x) ? x : 1);
    }

    //for (int i = 0; i < 6; ++i)
    //{
    //  data.push_back(i + 1);
    //}

    //std::cout << "data:[";
    //for (auto val : data)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    ProductTree pt(data);
    DataVector result = pt.Prod2();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";
    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    pt.ops_ = 0;
    result = pt.Prod();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    return 0;
}

Estoy agregando el algoritmo de @nore, para completar. Es realmente agradable y es el más rápido.

class ProductFlat
{
private:
    size_t ops_{ 0 };

    void InitTables(const DataVector& v, DataVector& left, DataVector& right)
    {
        if (v.size() < 2)
        {
            return;
        }

        left.resize(v.size() - 1);
        right.resize(v.size() - 1);

        auto l = left.begin();
        auto r = right.rbegin();
        auto ol = v.begin();
        auto or = v.rbegin();

        *l = *ol++;
        *r = *or++;
        if (ol == v.end())
        {
            return;
        }

        while (ol + 1 != v.end())
        {
            ops_ += 2;
            *l = *l++ * *ol++;
            *r = *r++ * *or++;
        }
    }

public:
    DataVector Prod(const DataVector& v)
    {
        if (v.size() < 2)
        {
            return v;
        }

        DataVector result, left, right;
        InitTables(v, left, right);

        auto l = left.begin();
        auto r = right.begin();
        result.push_back(*r++);
        while (r != right.end())
        {
            ++ops_;
            result.push_back(*l++ * *r++);
        }
        result.push_back(*l++);
        return result;
    }

    auto Ops() const
    {
        return ops_;
    }
};