Étant donné les nnombres dans un tableau (vous ne pouvez pas supposer que ce sont des entiers), je voudrais calculer le produit de tous les sous-ensembles de taille n-1.

Vous pouvez le faire en multipliant tous les nombres ensemble, puis en les divisant à tour de rôle, tant qu'aucun des nombres n'est nul. Cependant, à quelle vitesse pouvez-vous le faire sans division?

Si vous n'autorisez pas la division, quel est le nombre minimum d'opérations arithmétiques (par exemple multiplication et addition) nécessaires pour calculer le produit de tous les sous-ensembles de taille n-1?

De toute évidence, vous pouvez le faire en (n-1)*nmultiplications.

Pour clarifier, la sortie est ndifférents produits et les seules opérations en dehors de la lecture et de l' écriture à la mémoire sont permis la multiplication, l' addition et la soustraction.

Exemple

Si l'entrée a trois nombres 2,3,5, alors la sortie est trois nombres 15 = 3*5, 10 = 2*5et 6 = 2*3.

Critère gagnant

Les réponses devraient donner une formule exacte pour le nombre d'opérations arithmétiques que leur code utilisera en termes de n. Pour vous simplifier la vie, je vais simplement brancher n = 1000votre formule pour juger de son score. Le plus bas sera le mieux.

S'il est trop difficile de produire une formule exacte pour votre code, vous pouvez simplement l'exécuter n = 1000et compter les opérations arithmétiques dans le code. Une formule exacte serait cependant préférable.

Vous devez ajouter votre score pour n=1000à votre réponse pour une comparaison facile.

Python, 3 (n-2) opérations, score = 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)

Les tableaux leftet rightcontiennent les produits cumulés du tableau de gauche et de droite, respectivement.

EDIT: Preuve que 3 (n-2) est le nombre optimal d'opérations nécessaires pour n> = 2, si nous utilisons uniquement la multiplication.

Nous le ferons par induction; par l'algorithme ci-dessus, il suffit de prouver que pour n> = 2, 3 (n-2) est une borne inférieure du nombre de multiplications nécessaires.

Pour n = 2, nous avons besoin d'au moins 0 = 3 (2-2) multiplications, donc le résultat est trivial.

Soit n> 2, et supposons que pour n - 1 éléments, nous ayons besoin d'au moins 3 (n-3) multiplications. Considérons une solution pour n éléments avec k multiplications. Maintenant, nous supprimons le dernier de ces éléments comme s'il s'agissait de 1 et simplifions directement toutes les multiplications par lui. Nous supprimons également la multiplication conduisant au produit de tous les autres éléments, car celui-ci n'est pas nécessaire car il ne peut jamais être utilisé comme valeur intermédiaire pour obtenir le produit de n-2 des autres éléments, car la division n'est pas autorisée. Cela nous laisse avec l multiplications, et une solution pour n - 1 éléments.

Par hypothèse d'induction, nous avons l> = 3 (n-3).

Voyons maintenant combien de multiplications ont été supprimées. L'un d'eux était celui qui conduisait au produit de tous les éléments sauf le dernier. De plus, le dernier élément a été utilisé directement dans au moins deux multiplications: s'il a été utilisé dans un seul, alors il a été utilisé lors de la multiplication par un résultat intermédiaire consistant en un produit des autres éléments; disons, sans perte de généralité, ce résultat intermédiaire incluait le premier élément du produit. Ensuite, il n'y a aucun moyen d'obtenir le produit de tous les éléments sauf le premier, car chaque produit qui contient le dernier élément est soit le dernier élément, soit contient le premier élément.

Nous avons donc k> = l + 3> = 3 (n-2), prouvant le théorème revendiqué.

Haskell , score 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

Essayez-le en ligne!

Disons qu'on nous donne la liste [a,b,c,d,e,f,g,h]. Nous le groupons d'abord par paires [[a,b],[c,d],[e,f],[g,h]]. Ensuite, nous recurse sur la liste demi-taille pairsde leurs produits pour obtenirsubresults

[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 nous prenons le premier élément (c*d)*(e*f)*(g*h)et le multiplions par bet arespectivement, nous obtenons le produit de tout sauf aet de tout sauf b. En faisant cela pour chaque paire et résultat récursif avec cette paire manquante, nous obtenons le résultat final. Le cas de longueur impaire est spécialement traité en faisant passer l'élément impair non apparié à l'étape récursive, et le produit des éléments restants retournés est le produit sans lui.

Le nombre de multiplications t(n)est n/2pour le produit d'appariement, t(n/2)pour l'appel récursif et un autre npour les produits avec des éléments individuels. Cela donne t(n) = 1.5 * n + t(n/2)pour étrange n. Utiliser un décompte plus précis pour les impairs net ignorer la multiplication avec 1pour le cas de base donne un score 2997pour n=1000.

Haskell , score 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'

Essayez-le en ligne!

Une stratégie diviser pour mieux régner, qui rappelle beaucoup le tri par fusion. Ne fait aucune indexation.

La fonction partitiondivise la liste en deux moitiés aussi égales que possible en plaçant des éléments alternés sur les côtés opposés de la partition. Nous fusionnons récursivement les résultats (p,r)pour chacune des moitiés, avec rla liste des produits avec un manquant et ple produit global.

Pour la sortie de la liste complète, l'élément manquant doit se trouver dans l'une des moitiés. Le produit avec cet élément manquant est un produit manquant pour la moitié dans laquelle il se trouve, multiplié par le produit complet pour l'autre moitié. Ainsi, nous multiplions chaque produit avec un manquant par le produit complet de l'autre moitié et dressons une liste des résultats, au fur et à mesure map(*p1)r2 ++ map(*p2)r1). Cela prend des nmultiplications, où nest la longueur. Nous devons également créer un nouveau produit complet p1*p2pour une utilisation future, ce qui coûtera 1 multiplication supplémentaire.

Cela donne la récursion générale pour le nombre d'opérations t(n)avec nmême: t(n) = n + 1 + 2 * t(n/2). L'impaire est similaire, mais l'une des sous-listes est 1plus grande. En effectuant la récursivité, nous obtenons des n*(log_2(n) + 1)multiplications, bien que la distinction impaire / paire affecte cette valeur exacte. Les valeurs jusqu'à t(3)sont améliorées en ne se multipliant pas 1en définissant une variante (%)de ce (*)qui raccourcit le _*1ou les 1*_cas.

Cela donne des 9975multiplications pour n=1000. Je crois que la paresse de Haskell signifie que le produit global inutilisé dans la couche externe n'est pas calculé 9974; si je me trompe, je pourrais l'omettre explicitement.

Haskell , score 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]

Essayez-le en ligne!

Comment ça marche

Il s'agit d'une version nettoyée de l'algorithme de xnor qui traite le cas étrange de manière plus simple (modification: il semble que xnor l'ait nettoyé de la même manière):

[a, b, c, d, e, f, g] ↦
[a, bc, de, fg] ↦
[(bc) (de) (fg), a (de) (fg), a (bc) ( fg), a (bc) (de)] par récursivité ↦
[(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)] par récursivité ↦
[(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) opérations, score = 9974

Fonctionne avec un arbre binaire.

Python

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])

Cela nécessite également des opérations d'addition de liste et une certaine arithmétique sur les nombres qui ne sont pas les valeurs d'entrée; Je ne sais pas si cela compte. La mulfonction est là pour enregistrer n opérations pour le cas de base, pour éviter de les gaspiller en les multipliant par 1. Dans tous les cas, il s'agit d'O (n log n) opérations. Si seulement le comptage des opérations arithmétiques sur des nombres d'entrée, est, la formule exacte avec j = floor(log_2(n)): j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2.

Merci à @xnor d'avoir sauvé une opération avec l'idée de ne pas calculer le produit extérieur!

La dernière partie consiste à sortir les produits dans l'ordre du terme manquant.

O ((n-2) * n) = O (n ² ): Solution triviale

Ceci est juste la solution triviale qui multiplie ensemble chacun des sous-ensembles:

Python

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

Notez que cela nécessite également ndes opérations d'ajout de liste; Je ne sais pas si cela compte. Si cela n'est pas autorisé, vous product(array[:index] + array[index + 1:])pouvez le remplacer par product(array[:index]) * product(array[index + 1:]), ce qui change la formule en O((n-1)*n).

Python, 7540

Une stratégie de fusion tripartite. Je pense que je peux faire encore mieux que cela, avec une fusion encore grande. C'est O (n log n).

EDIT: correction d'une erreur de calcul.

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 fonction pertinente est missing_products, qui donne le produit global et tous ceux avec un élément manquant.

dc, score 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

Je suppose que la comparaison entière z1=(qui met fin à la récursivité lorsque nous atteignons la dernière valeur) est libre. C'est équivalent aux goûts de foreachdans d'autres langues.

Démonstrations

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

Une démo avec de grandes et petites entrées:

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

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

Cette implémentation utilise une table de recherche d'arbre binaire. Ma première implémentation a été O (NlogN), mais une optimisation de dernière minute, qui recherche le produit de tous les éléments du tableau moins une paire, + 2 multiplications ont sauvé la journée. Je pense que cela pourrait encore être optimisé un peu plus, peut-être encore 16% ...

J'ai laissé quelques traces de débogage, uniquement parce qu'il est plus facile de les supprimer que de les réécrire :)

[Modifier] la complexité réelle est mesurée à O ([2NlogN] / 3) pour 100. Elle est en fait un peu pire que O (NlogN) pour les petits ensembles, mais tend vers O ([NlogN] / 2) à mesure que le tableau grandit très grand O (0,57.NlogN) pour un ensemble de 1 million d'éléments.

#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;
}

J'ajoute l'algorithme de @ nore, pour être complet. C'est vraiment sympa et c'est le plus rapide.

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_;
    }
};