Fastest algorithm to take the product of all subsets
Python, 3(n-2) operations, 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)
The arrays left and right contain the cumulated products of the array from the left and from the right, respectively.
EDIT: Proof that 3(n-2) is the optimal number of operations needed for n >= 2, if we only use multiplication.
We will do that by induction; by the above algorithm, we just have to prove that for n >= 2, 3(n-2) is a lower bound on the number of multiplications needed.
For n = 2, we need at least 0 = 3(2-2) multiplications, so the result is trivial.
Let n > 2, and suppose for n - 1 elements, we need at least 3(n-3) multiplications. Consider a solution for n elements with k multiplications. Now, we remove the last of these elements as if it was 1, and simplify all multiplications directly by it. We also remove the multiplication leading to the product of all the other elements, since that one is not needed as it can never be used as an intermediate value to get the product of n-2 of the other elements, since division is not allowed. This leaves us with l multiplications, and a solution for n - 1 elements.
By induction hypothesis, we have l >= 3(n-3).
Now, let's have a look at how many multiplications were removed. One of them was the one leading to the product of all elements except the last. Moreover, the last element was used directly in at least two multiplications: if it was used in only one, then it was used when multiplying by an intermediate result consisting in some product of the other elements; let's say, without loss of generality, this this intermediate result included the first element in the product. Then, there is no way to get the product of all the elements but the first, since every product that contains the last element is either the last element, or contains the first element.
We thus have k >= l+3 >= 3(n-2), proving the claimed theorem.
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
Try it online!
Say we're given the list [a,b,c,d,e,f,g,h]. We first group it into pairs [[a,b],[c,d],[e,f],[g,h]]. Then, we recurse on the half-size list pairs of their products to get 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)]
If we take the first element (c*d)*(e*f)*(g*h), and multiply it by b and a respectively, we get the product of all but a and all but b. Doing this for every pair and recursive result with that pair missing, we get out final result. The odd-length case is specially handled by having the odd element passed unpaired to the recursive step, and the product of the remaining elements returned is the product without it.
The number of multiplications t(n) is n/2 for the pairing product, t(n/2) for the recursive call, and another n for the products with individual elements. This gives t(n) = 1.5 * n + t(n/2) for odd n. Using a more precise counts for odd n and ignoring multiplying with 1 for the base case gives score 2997 for 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'
Try it online!
A divide-and-conquer strategy, very reminiscent of merge sort. Doesn't do any indexing.
The function partition splits the list into as-equal-as-possible halves by putting alternating elements on opposite sides of the partition. We recursively merge the results (p,r) for each of the halves, with r the list of products-with-one-missing, and p the overall product.
For the output for the full list, the missing element must be in one of the halves. The product with that element missing is a one-missing-product for the half it's in, multiplied by the full product for the other half. So, we multiply each product-with-one-missing by the full product of the other half and make a list of the results, as map(*p1)r2 ++ map(*p2)r1). This takes n multiplications, where n is the length. We also need to make a new full-product p1*p2 for future use, costing 1 more multiplication.
This gives the general recursion for for the number of operations t(n) with n even: t(n) = n + 1 + 2 * t(n/2). The odd one is similar, but one of the sublists is 1 larger. Doing out the recursion, we get n*(log_2(n) + 1) multiplications, though the odd/even distinction affects that exact value. The values up to t(3) are improved by not multiplying by 1 by defining a variant (%) of (*) that shortcuts the _*1 or 1*_ cases.
This gives 9975 multiplications for n=1000. I believe Haskell's laziness means the unused overall product in the outer layer is not computed for 9974; if I'm mistaken, I could omit it explicitly.