挑选五个总和为S的数字

Question

给定一个数组A的N非负数,我感兴趣的是找到办法,你可以选择5个号码(数组中从不同的位置)的数量,使得它们的总和S.

有一个简单的解决方案O(N^3):

Let H be a hash table of (sum, position of leftmost element of sum)
for i = 0, N
    for j = i + 1, N
        H.add(A[i] + A[j], i)

numPossibilities = 0
for i = 0, N
    for j = i + 1, N
        for k = j + 1, N
            numPossibilities += H.get(S - (A[i] + A[j] + A[k]), k)

其中H.get(x, y)返回散列中元素的数量,其总和具有相同的散列,x并且其最左边的元素大于k.

或者,我们可以将3个元素的总和添加到哈希表中,然后继续使用2个嵌套for循环.然而,复杂性仍然相同,我们只使用更多内存.

假设输入是相当随机的(因此没有最坏情况的哈希),是否有一种算法可以解决这个问题,O(N^2)或者可能O(N^2 log N),或者即使O(N^3)它在所有情况下都能解决？我认为二进制搜索可能有所帮助,但我不知道如何处理重叠索引.

上述解决方案在实践中比天真的5-for-loop解决方案好很多,但是我觉得我们可以做得更好,因此这个问题.

如果您可以证明不存在这样的算法,那么如何优化上述解决方案？

澄清:

上面的算法确实是O(N^5)在最坏的情况下,例如当给定的数组只包含数字1时我们有S = 5.然而,平均而言,该H.get方法更接近于O(1),因此我的平均立方复杂度.

如果你实现这个并在一个很大的间隔(比如0到Int32.MaxValue)中的1000个随机数上运行它,你会发现它运行得相对较快.不过,找到需要很长时间的输入并不难.即使我们无法让所有相同数字的运行速度足够快,我们可以做出哪些优化？

在同样的假设下,我们可以做得更好,渐近或至少在实践中做得更好吗？

Answer 1

我认为数字必须有不同的位置这一事实是一个红色的鲱鱼.您可以使用包含 - 排除原则来计算所有位置(i,j,k,l,m)的数量,其中x [i] + x [j] + x [k] + x [l] + x [m ] = S和i,j,k,l,m是不同的:

 sums with i!=j,i!=k,i!=l...,l!=m  = all sums 
                                   - sums with i=j
                                   - ...
                                   - sums with l=m
                                   + sums with i=j and j=k
                                   + ...
                                   + sums with k=l and l=m
                                   - ...
                                   + sums with i=j=k=l=m

计算右边的和,除了第一个,在O(N ^ 2 log N)中是可行的.例如,要找到位置的数量(i,i,k,l,m),使得x [i] + x [i] + x [k] + x [l] + x [m] = S,你可以创建具有和{2a + b}和{c + d}的排序数组,并检查它们是否具有元素x,y,使得x + y = S.

主要算法

因此,计算有多少位置(i,j,k,l,m)就足够了,其中x[i]+x[j]+x[k]+x[l]+x[m]=Si,j,k,l,m不一定是不同的.基本上,您可以这样使用Moron的解决方案:

• 创建一个排序的和数组{a + b:a,b是数组中的数字}; 将相等的元素组合成一个,记住计数.例如,对于数组[1,1,3],您将获得形式为a + b的九个总和[2,2,2,2,4,4,4,4,6].然后你将相同的元素分组记住计数:[(2,4),(4,4),(6,1)].该步骤为O(N ^ 2 log N).

• 对于每个e,计算数组中与Se相加的元素对数.在Moron的解决方案中,你有两个指针,一个向右,一个向左.如果总和太低,移动第一个指针增加总和; 如果总和太高,移动第二个指针减少它.

  假设总和是正确的.这意味着一个指向(a,x),第二个指向(b,y),其中a + b = Se.通过x*y增加计数器并移动两个指针(您只能移动一个指针,但在下一步中将没有匹配,然后第二个指针将被移动.).

例如,对于[(2,4),(4,4),(6,1)]数组和Se = 8,第一个指针指向(2,4),第二个指针指向(6,1).由于2 + 6 = 8,你添加4并移动两个指针.现在他们都指向(4,4),所以你将计数器增加16点.不要停止!指针相互传递,你首先得到(6,1),第二次得到(2,4),将计数器增加4.

所以,最后,有4 + 16 + 4 = 24种方法可以得到8作为[1,1,3]的4个元素的总和:

>>> len([k for k in itertools.product([1,1,3],repeat=4) if sum(k) == 8])
24

Prelude Control.Monad> length [k | k <- replicateM 4 [1,1,3], sum k == 8]
24

对每个e重复一次,你将获得将S作为5个元素之和的方法.

对于[1,1,1,1,1]和Se = 4,sums数组将是[(2,25)],你可以得到625种方法来得到4的总和.

对于每个e,该步骤在阵列的大小上是线性的(因此它是O(N ²)),因此循环取O(N ³).

关于包含 - 排除:

如果x [i] + x [j] + x [k] + x [1] + x [m] = S,则调用五元组(i,j,k,l,m)"正确".目标是计算正确五元组的数量(i,j,k,l,m),其中i,j,k,l,m是成对不同的.主算法可以在O(N ^ 3)中计算有多少有适当的五元组,其中不一定有不同的组件.剩下的事情是计算那些"错误的"元组.

考虑适当五元组的子集

一个_xy = {(i,j,k,l,m):第x和第y位的索引是相同的}

例如,A ₂₄是一组适当的五元组(i,j,k,l,m),其中j = 1.

错误的五元组是:

一个₁₂ ∪一个₁₃ ∪...∪一₄₅

通过包含 - 排除来计算其基数:

| A ₁₂ ∪一个₁₃ ∪...∪一个₄₅ | = | A ₁₂ | + | A ₁₃ | + ... + | A ₄₅ | - | A ₁₂ ∩一个₂₃ | - ... - | A ₃₄ ∩一个₄₅ | + ... + | A ₁₂ ∩甲₂₃ ∩...∩甲₃₅ ∩甲₄₅ |

这里有2 ¹⁰ = 1024个加数.但是很多基数都是一样的.

你唯一需要考虑的事情是:

• X ₁ = | A ₁₂ | - i = j的五倍
• X ₂ = | A ₁₂ ∩甲₂₃ | - i = j = k的五元组
• X ₃ = | A ₁₂ ∩甲₂₃ ∩甲₃₄ | - i = j = k = 1的五元组
• X ₄ = | A ₁₂ ∩甲₂₃ ∩甲₃₄ ∩甲₄₅ | - 五元组,其中i = j = k = l = m
• X ₅ = | A ₁₂ ∩甲₃₄ | - 五元组,i = j,k = l
• X ₆ = | A ₁₂ ∩甲₂₃ ∩甲₄₅ | - 五元组,其中i = j = k,l = m

您可以通过置换来观察此处所有其他集合.例如,A ₂₄具有与A ₁₂相同的基数.

计算这6套的基数相当容易.对于第一个,您创建数组{2a + b}和{c + d}并计算有多少共同元素; 对于其他的,只有3个或更少的自由变量,所以即使是一个简单的循环也会给你O(N ^ 3).

为了简化总和,我编写了以下Haskell程序:

import Control.Monad
import Data.List
import qualified Data.Map as Map

-- Take equivalence relation, like [(1,2),(2,3)] and return its partition, like [3,1,1]
f xs = sort $ map length $ foldr f (map return [1..5]) xs
       where f (x,y) a = let [v1] = filter (x `elem`) a
                             [v2] = filter (y `elem`) a
                         in if v1 == v2 then a else (a \\ [v1,v2]) ++ [v1++v2]

-- All 1024 subsets of [(1,2),(1,3), ..., (4,5)]
subsets = filterM (const [False, True]) [(i,j) | i <- [1..5], j <- [i+1..5]]

res = Map.fromListWith (+) $ map (\k -> (f k, (-1)^(length k))) subsets

*Main> res
Loading package array-0.3.0.1 ... linking ... done.
Loading package containers-0.3.0.0 ... linking ... done.
fromList [([1,1,1,1,1],1),([1,1,1,2],-10),([1,1,3],20),([1,2,2],15),([1,4],-30),([2,3],-20),([5],24)]

这意味着公式是

所有子集 - 10X ₁ + 20X ₂ - 30X ₃ + 24X ₄ + 15X ₅ - 20X ₆.

校验:

[0,0,0,...,0]总共有多少个五元组？计算的一种方法是直接计算,第二种方法是使用公式(而不关心不同的位置):

direct x = x*(x-1)*(x-2)*(x-3)*(x-4)
indirect x = x^5 - 10 * x^4 + 20 * x^3 + 15 * x^3 - 30 * x^2 - 20*x^2 + 24*x

*Main> direct 100
9034502400
*Main> indirect 100
9034502400

其他评论:

此外,还有O(一个_n log a _n)解:使用FFT 计算(x ^{a ₁} + ... + x ^{a _n})⁵,结果是x ^S处的系数.这允许一些_i被使用两次,但你可以根据包含减去像(x ^{2a ₁} + ... + x ^{2a _n})⁵*(x ^{a ₁} + ... + x ^{a _n})³等多项式 - 排除原则.

在一些受限制的计算模型中,已经表明该问题的决策版本需要O(N ^ 3)时间.