如何在n个长度的数组中找到k个元素的最高乘积，其中k <ñ [英] How to find highest product of k elements in an array of n length, where k &lt; n

问题描述

我最近尝试了3个元素的最高乘积的问题.现在，我正在尝试针对k个元素执行此操作.假设现在从3开始，它需要4个元素.我试图编写一个通用函数，以便它可以处理数组中的任何k个元素.算法必须位于O(n)中，就像具有3个元素的算法一样.

I recently tried the question for the highest product of 3 elements. Now I am trying to do it for the k elements. Let's say from 3 now it is asking for 4 elements. I tried to write a generic function so it could handle for any k elements within the array. The algo has to be in O(n) just like the one with 3 elements is.

 def highest_product_sol(input):

    high = max(input[0],input[1])
    low = min(input[0],input[1])


    max_prod_2 = input[0] * input[1]
    low_prod_2 = input[0] * input[1]
    max_prod_3 = max_prod_2 * input[2]


    prod_2_high = input[0] * input[1]
    prod_2_low = input[0] * input[1]

    for i in range(2,len(input)):
        val = input[i]
        max_prod_3 = max(max_prod_3,max_prod_2*val,low_prod_2*val)

        prod_2_high = high * val
        prod_2_low =  low * val

        max_prod_2 = max(max_prod_2,prod_2_high)

        low_prod_2 = min(low_prod_2,prod_2_high)


        high = max(high,val)

        low = min(low,val)


    return (max_prod_2,low_prod_2,max_prod_3)

def highest_product_num(input,num):


    high = max(input[0:num - 1])
    low = min(input[0:num - 1])


    print("max",high)
    print("min",low)

    prod_high_minus_1 = 1
    prod_low_minus_1 = 1

    for n in range(0,num-1):
        prod_high_minus_1 *= input[n]
        prod_low_minus_1 *= input[n]

    max_prod_n_1 = prod_high_minus_1
    min_prod_n_1 = prod_high_minus_1
    max_prod_n = prod_high_minus_1 * input[num-1]

    for i in range(num,len(input)):
        val = input[i]
        max_prod_n = max(max_prod_n,max_prod_n_1*val,min_prod_n_1*val)

        prod_high_minus_1 = high * val
        prod_low_minus_1 =  low * val

        max_prod_n_1 = max(max_prod_n_1,prod_high_minus_1)

        min_prod_n_1 = min(min_prod_n_1,prod_low_minus_1)


        high = max(high,val)

        low = min(low,val)

    return max_prod_n
test_input = [[1,2,3,4,5,6,7,8],[1,-2,3,4,5,100,2,3,1],[-10,-10,1,3,2][1000,7,-6,2,2]]
print(test_input)

for i in test_input:
    print(highest_product_num(i,4),"\n")

# correct `results`
# 1680
# 6000
# 600

推荐答案

numpy 中的O(n)解决方案，在4个示例列表和@Stefan Pochmann的无情自动测试脚本中进行了压力测试.非常感谢Stefan，如果没有Stefan的投入，就会发现一些严重的错误.

O(n) solution in numpy, stress-tested on the 4 example lists and @Stefan Pochmann's merciless auto test script. Big thanks to Stefan, without whose input a couple of severe bugs would have gone unnoticed.

import numpy as np

def kmaxprod_v2(data, k):
    if len(data) < k:
        return np.nan
    data = np.asanyarray(data)
    # for integer dtypes convert to python ints to have unlimited range for the
    # final product
    dfp = data.astype(object) if data.dtype in (
        int, np.int64, np.int32, np.int16, np.int8) else data
    # np.argpartition raises an exception if len(data) == k, therefore
    if len(data) == k:
        return np.prod(dfp)
    neg = data <= 0
    # if k is odd and there are no positive elements we must settle for the
    # least negative
    if k % 2 == 1 and np.count_nonzero(neg) == len(data):
        return np.prod(-np.partition(-data, k)[:k].astype(dfp.dtype))
    # now n > k and we have at least one positive element
    ap = np.argpartition(-np.absolute(data), k)
    low, high = ap[k:], ap[:k]
    # try multiplying the k with highest absolute value
    greedy = np.prod(dfp[high])
    if greedy >= 0:
        return greedy
    # there are two possible ways of fixing the sign:
    # either swap the worst negative inside for the best positive outside
    # or swap the worst positive inside for the best negative outside
    # compute both and compare
    # bpo in, wni out
    bpo = np.max(dfp[low])
    if bpo <= 0:
        spfn = 0
    else:
        neg_high = np.where(neg[high])[0]
        wni_ind = np.argmax(data[high[neg_high]])
        # translate to index in high
        wni_ind = neg_high[wni_ind]
        spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]])
    # bno in, wno out
    pos_high = np.where(~neg[high])[0]
    if len(pos_high) == 0:
        snfp = 0
    else:
        wpi_ind = np.argmin(data[high[pos_high]])
        wpi_ind = pos_high[wpi_ind]
        bno = np.min(dfp[low])
        snfp = bno*np.prod(dfp[high[:wpi_ind]])*np.prod(dfp[high[wpi_ind+1:]])
    return max(spfn, snfp)

算法简述:

• 特殊情况k为奇数，所有数据为负，按分区找到k最小为负，返回prod，停止
• 按绝对值划分，并使用内省选择库功能在k-O(n)最坏情况下进行划分
• 如果prod top k> = 0，则停止
• 如果可能的话，将最小的正数内部交换为最大的负数外部，存储产品
• 如果可能，将最小的负数内部交换为最大的正数外部，请存储产品
• 返回上述最佳状态，停止

样品运行:

>>> test_input = [[1,2,3,4,5,6,7,8],[1,-2,3,4,5,100,2,3,1],[-10,-10,1,3,2],[1000,7,-6,2,2]]
>>> for t in test_input:
...     kmp.kmaxprod(t,4)
... 
1680
6000
600
28000

测试脚本，谢谢@Stefan Pochmann

Test script, thanks @Stefan Pochmann

import itertools, operator, functools, time
def naive(data, k):
    return max(functools.reduce(operator.mul, comb) for comb in itertools.combinations(data, k))

test_input = [([1,2,3,4,5,6,7,8], 4), ([1,-2,3,4,5,100,2,3,1], 4),
              ([-10,-10,1,3,2], 4), ([1000,7,-6,2,2],4),
              ([-1, 0, 1], 2), ([2, 5, 8, 9, 1, 3, 7], 4),
              ([-1, -1, 2, 1], 2), ([-1000, -1, 2, 3], 2),
              ([3, 5, 2, 8, 3], 2), ([-1000, -1, 2, 3, 4, 5, 6, 7], 2)]

for t, k in test_input:
    print(t, k, kmaxprod_v2(t, k), naive(t, k))

ne = 0
t = np.zeros((3,))
import random
for k in range(2, 20):
  for n in range(k, 24):
    print('n =', n, ': k =', k, 'errors:', ne, 'total time O(n), naive:', np.diff(t))
    for _ in range(100):
        data = [random.randrange(-14, 15) for _ in range(n)]
        t[0] += time.time()
        a = kmaxprod_v2(data, k)
        t[1] += time.time()
        b = naive(data, k)
        t[2] += time.time()
        if a != b:
            ne += 1
            print(data, k, a, b)

这篇关于如何在n个长度的数组中找到k个元素的最高乘积，其中k <ñ的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！