动态规划：产品总和

StackOverflow https://stackoverflow.com/questions/1814466

题

假设您有两个相同长度的列表，L1和L2，N。我们将prodSum定义为：

def prodSum(L1, L2) :
    ans = 0
    for elem1, elem2 in zip(L1, L2) :
        ans += elem1 * elem2

    return ans

是否存在一种有效的算法，假设L1被排序，L2的排列数使得prodSum（L1，L2）<！> lt;一些预先指定的值？

如果它可以简化问题，你可以假设L1和L2都是来自[1,2，...，N]的整数列表。

编辑：Managu的回答让我确信，如果不假设L1和L2是来自[1,2，...，N]的整数列表，这是不可能的。我仍然对采用这种约束的解决方案感兴趣。

有帮助吗？

解决方案

我想首先消除对数学的一定程度的混淆，然后讨论两个解决方案，并为其中一个提供代码。

有一个名为#P的计数类，它与是 - 否类NP非常相似。从定性的角度来说，它比NP更难。没有特别的理由相信这个计数问题比＃P-hard更好，尽管证明这一点可能很难或很容易。

然而，许多＃P-hard问题和NP难问题在实践中需要花费多长时间才能解决，甚至一个特定的难题也可能更难或更容易，具体取决于输入的属性。 NP-hard或＃P-hard意味着存在困难的案例。一些NP难题和#P难题也有较少的难题甚至是直接容易的案例。 （其他人的案例似乎比最难的案件容易得多。）

因此，实际问题可能在很大程度上取决于感兴趣的输入。假设阈值位于高端或低端，或者您有足够的内存来获得相当数量的缓存结果。然后有一个有用的递归算法，它使用了两个想法，其中一个已经提到：（1）在部分分配了一些值之后，列表片段的剩余阈值可以排除所有排列，也可以允许所有这些排列。 （2）内存允许，你应该缓存一些剩余的阈值和一些列表片段的小计。要改进缓存，您还可以按顺序从其中一个列表中选择元素。

这是一个实现此算法的Python代码：

list1 = [1,2,3,4,5,6,7,8,9,10,11]
list2 = [1,2,3,4,5,6,7,8,9,10,11]
size = len(list1)
threshold = 396     # This is smack in the middle, a hard value

cachecutoff = 6     # Cache results when up to this many are assigned

def dotproduct(v,w):
    return sum([a*b for a,b in zip(v,w)])

factorial = [1]
for n in xrange(1,len(list1)+1):
    factorial.append(factorial[-1]*n)

cache = {}

# Assumes two sorted lists of the same length

def countprods(list1,list2,threshold):
    if dotproduct(list1,list2) <= threshold:            # They all work
        return factorial[len(list1)]
    if dotproduct(list1,reversed(list2)) > threshold:   # None work
        return 0
    if (tuple(list2),threshold) in cache:               # Already been here
        return cache[(tuple(list2),threshold)]
    total = 0
    # Match the first element of list1 to each item in list2
    for n in xrange(len(list2)):
        total += countprods(list1[1:],list2[:n] + list2[n+1:],
            threshold-list1[0]*list2[n])
    if len(list1) >= size-cachecutoff:
        cache[(tuple(list2),threshold)] = total
    return total

print 'Total permutations below threshold:',
print countprods(list1,list2,threshold)
print 'Cache size:',len(cache)

正如评论专栏所说，我用这个阈值的硬值测试了这段代码。它比所有排列的天真搜索快得多。

如果满足三个条件，还有另一种算法优于此算法：（1）没有足够的内存用于良好的缓存，（2）列表条目是小的非负整数，（3）你对最难的门槛感兴趣。使用第二种算法的第二种情况是，如果您希望所有阈值的计数变平，无论是否满足其他条件。要将此算法用于两个长度为n的列表，首先选择一个基数x，它是10或2的幂，大于n阶乘。现在制作矩阵

M[i][j] = x**(list1[i]*list2[j])

如果使用 Ryser公式计算此矩阵M的永久性，则第k位数基数x中的永久物的数字告诉您点积正好为k的排列数。此外，Ryser公式比直接对所有排列求和要快得多。 （但它仍然是指数级的，所以它与计算永久物是＃P-hard的事实并不矛盾。）

此外，是的，这组排列是对称组。如果你能以某种方式使用群论来加速这个计数问题，那就太好了。但据我所知，这个问题的描述没有任何深刻的内容。

最后，如果不是精确计算低于阈值的排列数，而只是想近似那个数字，那么游戏可能会完全改变。 （你可以在多项式时间内逼近永久物，但这在这里没有用。）我必须考虑做什么;无论如何，这不是提出的问题。

我意识到上面的讨论和上面的代码中缺少另一种缓存/动态编程。代码中实现的缓存是早期缓存：如果只将list1的前几个值分配给list2，并且如果剩余阈值多次出现，则缓存允许代码重用结果。如果list1和lis的条目，这很好用t2是不太大的整数。但如果条目是典型的浮点数，它将是一个失败的缓存。

但是，当分配了list1的大部分值时，您也可以在另一端预先计算。在这种情况下，您可以为所有剩余值创建小计的排序列表。请记住，您可以按顺序使用list1，并在list2端执行所有排列。例如，假设list1的最后三个条目是[4,5,6]，并且假设list2中的三个值（中间的某个位置）是[2.1,3.5,3.7]。然后，您将缓存六个点产品的排序列表：

endcache[ [2.1, 3.5, 3.7] ] = [44.9, 45.1, 46.3, 46.7, 47.9, 48.1]

这对你有什么用？如果你查看我发布的代码，函数countprods（list1，list2，threshold）以递归方式使用子阈值。第一个参数list1可能更好地作为全局变量而不是作为参数。如果list2足够短，那么countprods可以通过在listcache [list2]列表中进行二进制搜索来更快地完成工作。 （我刚刚从stackoverflow中了解到这是在Python的bisect模块中实现的，尽管性能代码无论如何都不会用Python编写。）与头缓存不同，即使有头缓存，最终缓存也可以加速代码。 list1和list2的条目之间没有数字重合。 Ryser的算法在没有数字重合的情况下也很难找到这个问题，所以对于这种类型的输入，我只看到两个加速度：使用<！>“全部<！>”来搜索搜索树的一个分支。 test和<！> quot; none <！> quot;测试和结束缓存。

其他提示

可能没有（没有简化的假设）：你的问题是NP-Hard。这是 SUBSET-SUM 的简单缩减。设count_perms(L1, L2, x)表示函数<！>“;计算L2的排列数，使得prodSum（L1，L2）<！> lt; <！> X QUOT; 

SUBSET_SUM(L2,n): # (determine if any subset of L2 adds up to n)
    For i in [1,...,len(L2)]
        Set L1=[0]*(len(L2)-i)+[1]*i
        calculate count_perms(L1,L2,n+1)-count_perms(L1,L2,n)
        if result positive, return true
    Return false

因此，如果有办法有效地计算你的函数<=>，那么我们将有一个有效的算法来计算SUBSET_SUM（L2，n）。

这也证明是一个抽象的代数问题。这对我来说已经有一段时间了，但这里有一些事情要开始。关于以下内容没有什么特别重要的（这是非常基本的;扩展了每个组与排列组同构的事实），但它提供了一种不同的方式来查看问题。

我会尝试坚持使用相当标准的符号：<！>“ x <！>”;是一个向量，<！>“ x i <！>”;是 x 的i th 组件。如果<！>“L <！>”;是一个列表， L 是等效矢量。 QUOT <！>的 1 名词 QUOT <！>;是一个包含所有分量= 1的向量。自然数的集合<！>＃8469;被认为是正整数。 <！> QUOT; [A，B] QUOT <！>;是从a到b的整数集，包括。 <！>“<！>＃952;（ x ， y ）<！>”;是 x 和 y

形成的角度

注意prodSum是点积。问题相当于找到L2上的操作（置换元素）生成的所有向量 L ，使得<！>＃952;（ L1 ， L ）小于一个给定的角度<！>＃945;。该操作相当于通过带有表示的子空间反映<！>＃8469; n 中的一个点：

  

LT <！>; <！>＃8469; n | （<强> X <子> I <强> X <子>Ĵ -1 ）<子>（I，J ）<！>＃8712; A <！> gt;

其中i和j在[1，n]中，A至少有一个元素且没有（i，i）在<=>中（即<=>是[1，非自反的子集] n] 2 其中| <=> | <！> gt; 0）。更明确地（并且更模糊地）陈述，子空间是一个或多个组件等于一个或多个其他组件的点。反射对应于矩阵，其列是所有标准基矢量。

让我们将反射组命名为<！>“RP n <！>”; （它应该有另一个名字，但内存失败）。 RP n 与对称组S n 同构。因此

  

| RP <子>名词 | = | S n | = n！

在3维中，这给出了一组6阶。反射组是D 3 ，三角形对称组，作为立方体对称组的子组。事实证明，你也可以通过 L2 以<！>＃960; / 3的增量旋转 1 n 来生成点。这是模块化组<！>＃8484; 6 ，这指出了一个可能的解决方案：找到一组n阶！使用最少数量的生成器并使用它来生成L2的排列作为序列，其中 L2 增加，然后减小，角度。从那里，我们可以尝试使用<！>＃952生成元素 L ;（ L1 ， L ）<！> lt; <！>＃945;直接（例如我们可以在每个序列的前半部分进行binsearch以找到转换点;使用它，我们可以指定满足条件的其余序列并在O（1）时间内计算它）。我们称这个组为RP' n 。

RP' 4 由4个子空间构成，与<！>＃8484; 6 同构。更一般地，RP' n 由n个子空间构成，与RP' n-1 同构。

这是我的抽象代数肌肉真正开始失败的地方。我会继续努力进行施工，但是Managu的回答并没有留下太多希望。我担心将RP 3 减少到<！>＃8484; 6 是我们可以做出的唯一有用的减少。

看起来如果l1和l2都被排序为高 - <！> gt;低（或低 - <！> gt;高，无论如何，如果它们具有相同的顺序），结果最大化，如果它们是有序的，结果是最小化的，秩序的其他改变似乎遵循一些规则;在连续的整数列表中交换两个数字总是将总和减少一个固定的数量，这似乎与它们的距离相关（即交换1和3或2和4具有相同的效果）。这只是一点点麻烦，但想法是有一个最大值，一个最小值，如果它们之间有一些预先指定的值，就有办法计算使这种情况成为可能的排列（尽管如果;列表不是均匀间隔，然后没有。好吧，不是我所知道的。如果l2是（1 2 4 5）交换1 2和2 4会产生不同的影响）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top