Biorąc pod uwagę nliczby w tablicy (nie można zakładać, że są to liczby całkowite), chciałbym obliczyć iloczyn wszystkich podzbiorów wielkości n-1.

Możesz to zrobić, mnożąc wszystkie liczby, a następnie dzieląc je kolejno, o ile żadna z liczb nie jest równa zero. Jak szybko możesz to zrobić bez podziału?

Jeśli nie pozwalasz na dzielenie, jaka jest minimalna liczba operacji arytmetycznych (np. Mnożenie i dodawanie) potrzebnych do obliczenia iloczynu wszystkich podzbiorów wielkości n-1?

Oczywiście możesz to zrobić w (n-1)*nmultiplikacjach.

Aby wyjaśnić, dane wyjściowe są nróżnymi produktami, a jedynymi dozwolonymi operacjami oprócz odczytu i zapisu do pamięci są mnożenie, dodawanie i odejmowanie.

Przykład

Jeżeli wejście ma trzy numery 2,3,5, to wyjście jest trzy numery 15 = 3*5, 10 = 2*5i 6 = 2*3.

Kryterium wygranej

Odpowiedzi powinny zawierać dokładną formułę liczby operacji arytmetycznych, których użyje ich kod n. Aby ułatwić życie, po prostu podłączę się n = 1000do twojej formuły, aby ocenić jej wynik. Im niższy, tym lepiej.

Jeśli zbyt trudno jest stworzyć dokładną formułę dla swojego kodu, możesz po prostu uruchomić go n = 1000i policzyć operacje arytmetyczne w kodzie. Dokładna formuła byłaby jednak najlepsza.

Powinieneś dodać swój wynik n=1000do swojej odpowiedzi w celu łatwego porównania.

Python, 3 (n-2) operacje, wynik = 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)

Tablice lefti rightzawierają skumulowane produkty tablicy odpowiednio z lewej i prawej strony.

EDYCJA: Dowód, że 3 (n-2) jest optymalną liczbą operacji potrzebnych dla n> = 2, jeśli używamy tylko mnożenia.

Zrobimy to przez indukcję; powyższym algorytmem musimy tylko udowodnić, że dla n> = 2, 3 (n-2) stanowi dolną granicę liczby potrzebnych mnożenia.

Dla n = 2 potrzebujemy co najmniej 0 = 3 (2-2) krotności, więc wynik jest trywialny.

Niech n> 2 i załóżmy, że dla elementów n - 1 potrzebujemy co najmniej 3 (n-3) mnożenia. Rozważ rozwiązanie n elementów z k mnożeniem. Teraz usuwamy ostatni z tych elementów, tak jakby to był 1, i bezpośrednio upraszczamy wszystkie multiplikacje. Usuwamy również mnożenie prowadzące do iloczynu wszystkich pozostałych elementów, ponieważ ten nie jest potrzebny, ponieważ nigdy nie można go użyć jako wartości pośredniej do uzyskania iloczynu n-2 pozostałych elementów, ponieważ podział nie jest dozwolony. To daje nam mnożenie 1 i rozwiązanie dla n - 1 elementów.

Zgodnie z hipotezą indukcyjną mamy l> = 3 (n-3).

Teraz rzućmy okiem na to, ile multiplikacji zostało usuniętych. Jednym z nich był ten, który doprowadził do iloczynu wszystkich elementów oprócz ostatniego. Co więcej, ostatni element został użyty bezpośrednio w co najmniej dwóch multiplikacjach: jeśli został użyty tylko w jednym, to został użyty przy pomnożeniu przez wynik pośredni składający się z iloczynu innych elementów; powiedzmy, bez utraty ogólności, ten pośredni wynik obejmował pierwszy element produktu. Zatem nie ma sposobu na uzyskanie iloczynu wszystkich elementów oprócz pierwszego, ponieważ każdy produkt, który zawiera ostatni element, jest albo ostatnim elementem, albo zawiera pierwszy element.

Mamy zatem k> = l + 3> = 3 (n-2), co dowodzi twierdzonego twierdzenia.

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

Wypróbuj online!

Powiedzmy, że dostaliśmy listę [a,b,c,d,e,f,g,h]. Najpierw grupujemy je w pary [[a,b],[c,d],[e,f],[g,h]]. Następnie powracamy do listy pairsproduktów o pół wielkości , aby uzyskaćsubresults

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

Jeżeli weźmiemy pod uwagę pierwszy element (c*d)*(e*f)*(g*h), i pomnożyć przez bi aodpowiednio, otrzymujemy produkt o wszystkich, ale ai wszystkich, ale b. Robiąc to dla każdej pary i wyniku rekurencyjnego z brakującą parą, otrzymujemy wynik końcowy. Przypadek nieparzystej długości jest obsługiwany w specjalny sposób, gdy nieparzysty element jest przekazywany niesparowany do kroku rekurencyjnego, a iloczyn pozostałych elementów jest produktem bez niego.

Liczba mnożeń t(n)dotyczy n/2produktu parowania, t(n/2)połączenia rekurencyjnego, a drugiego ndla produktów z pojedynczymi elementami. To daje t(n) = 1.5 * n + t(n/2)dziwne n. Użycie bardziej precyzyjnego liczenia dla nieparzystych ni ignorowanie mnożenia 1dla przypadku podstawowego daje wynik 2997dla n=1000.

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

Wypróbuj online!

Strategia „dziel i rządź”, bardzo przypominająca rodzaj scalania. Nie wykonuje żadnego indeksowania.

Ta funkcja partitiondzieli listę na możliwie równe połowy, umieszczając naprzemienne elementy po przeciwnych stronach partycji. Rekurencyjnie łączymy wyniki (p,r)dla każdej z połówek, z rlistą produktów z jednym brakującym i pogólnym produktem.

W przypadku danych wyjściowych pełnej listy brakujący element musi znajdować się w jednej z połówek. Produkt, w którym brakuje tego elementu, to produkt, w którym brakuje połowy jego połowy, pomnożony przez pełny produkt dla drugiej połowy. Tak więc mnożymy każdy brakujący produkt przez pełny produkt drugiej połowy i tworzymy listę wyników, as map(*p1)r2 ++ map(*p2)r1). Wymaga to nmnożenia, gdzie njest długość. Musimy także stworzyć nowy pełny produkt p1*p2do przyszłego użytku, kosztując 1 dodatkowy mnożenie.

Daje to ogólny dla rekursji dla liczby operacji t(n)z njeszcze: t(n) = n + 1 + 2 * t(n/2). Dziwny jest podobny, ale jedna z podlist jest 1większa. Wykonując rekurencję, otrzymujemy n*(log_2(n) + 1)mnożenia, chociaż rozróżnienie nieparzyste / parzyste wpływa na tę dokładną wartość. Wartości aż do t(3)są poprawione przez pomnożenie przez nie 1definiując wariant (%)z (*)tym, że Skróty _*1lub 1*_przypadkach.

Daje to 9975mnożenia dla n=1000. Uważam, że lenistwo Haskella oznacza, że ​​nieużywany ogólny produkt w zewnętrznej warstwie nie jest obliczany 9974; jeśli się mylę, mogę to pominąć.

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

Wypróbuj online!

Jak to działa

To jest oczyszczona wersja algorytmu xnor, która zajmuje się nieparzystym przypadkiem w bardziej prosty sposób (edycja: wygląda na to, że xnor wyczyścił go w ten sam sposób):

[a, b, c, d, e, f, g] ↦
[a, bc, de, fg] ↦
[(bc) (de) (fg), a (de) (fg), a (bc) ( fg), a (bc) (de)] przez rekurencję ↦
[(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)] przez rekurencję ↦
[(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].

Operacje O (n log n), wynik = 9974

Działa z drzewem binarnym.

Pyton

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

Wymaga to również operacji dodawania listy i pewnej arytmetyki liczb, które nie są wartościami wejściowymi; nie jestem pewien, czy to się liczy. mulFunkcja jest tam, aby zaoszczędzić n operacje dla przypadku bazowego, aby uniknąć marnowania ich przez pomnożenie przez 1. W każdym przypadku jest to O (n log n) operacji. Dokładna formuła jest, jeśli tylko licząc operacji arytmetycznych na liczbach wejściowego, j = floor(log_2(n)): j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2.

Dzięki @xnor za uratowanie jednej operacji z pomysłem nie obliczania zewnętrznego produktu!

Ostatnią częścią jest wyprowadzenie produktów w kolejności brakującego terminu.

O ((n-2) * n) = O (n ² ): Trywialne rozwiązanie

To tylko trywialne rozwiązanie, które zwielokrotnia każdy z podzbiorów:

Pyton

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

Zauważ, że wymaga to również noperacji dodawania listy; nie jestem pewien, czy to się liczy. Jeśli nie jest to dozwolone, product(array[:index] + array[index + 1:])można je zastąpić product(array[:index]) * product(array[index + 1:]), co zmienia formułę na O((n-1)*n).

Python, 7540

Trójstronna strategia scalania. Myślę, że mogę zrobić nawet lepiej niż to, z jeszcze dużym połączeniem. To O (n log n).

EDYCJA: Naprawiono błędne konto.

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)

Odpowiednią funkcją jest missing_products, która daje ogólny produkt i wszystkie z brakującym elementem.

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

Zakładam, że porównanie liczb całkowitych z1=(które kończy rekurencję po osiągnięciu ostatniej wartości) jest bezpłatne. Jest to równoważne z podobnymi foreachw innych językach.

Pokazy

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

Demo z dużymi i małymi wejściami:

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

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

Ta implementacja korzysta z tabeli wyszukiwania drzewa binarnego. Moją pierwszą implementacją było O (NlogN), ale optymalizacja w ostatniej chwili, która sprawdza iloczyn wszystkich elementów tablicy minus para, + 2 mnożenia uratowało dzień. Myślę, że można to jeszcze trochę zoptymalizować, może kolejne 16% ...

Zostawiłem trochę śladów debugowania, tylko dlatego, że łatwiej je usunąć niż przepisać :)

[Edytuj] rzeczywista złożoność jest mierzona przy O ([2NlogN] / 3) dla 100. W rzeczywistości jest nieco gorsza niż O (NlogN) dla małych zestawów, ale zmierza w kierunku O ([NlogN] / 2) wraz ze wzrostem tablicy bardzo duże O (0,57.NlogN) dla zestawu 1 miliona elementów.

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

Dla kompletności dodam algorytm @ nore. To naprawdę miłe i najszybsze.

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