动态编程:产品总和

Question

假设你有两个列表，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) <某个预先指定的值？

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

编辑:Managu的答案让我相信，如果不假设L1和L2是来自1，2，...，N的整数列表，这是不可能的。我仍然对假设这个约束的解决方案感兴趣。

Answer 1

我想首先消除一些数学上的困惑，然后讨论两个解决方案，并给出其中一个的代码。

有一个名为#P的计数类，它很像是-否类NP。在定性的意义上，它甚至比NP更难。没有特别的理由相信这个计数问题比#P-hard更好，尽管它可能很难或很容易证明这一点。

然而，许多#P-hard问题和NP-hard问题在实践中需要多长时间才能解决，而且甚至一个特定的困难问题也可能更难或更容易，这取决于输入的属性。NP-hard或#P-hard的意思是有困难的情况。一些NP-hard和#P-hard问题也有较少的困难情况，甚至是非常简单的情况。(其他人的情况似乎比最困难的情况要容易得多。)

因此，实际问题可能在很大程度上取决于兴趣的输入。假设阈值是偏高或偏低，或者您有足够的内存来存储相当数量的缓存结果。然后有一个有用的递归算法，它利用了两个想法，其中一个已经提到：(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的两个列表使用此算法，首先选择一个比n阶乘大的10或2的幂的基数x。现在制作矩阵

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

如果你使用Ryser formula计算矩阵M的永久值，那么基数x中的永久值的第k位告诉你点积恰好是k的排列的个数。而且，里瑟公式比直接对所有排列求和要快得多。(但它仍然是指数型的，因此它与计算永久数是#P-hard的事实并不矛盾。)

而且，是的，排列的集合是对称群是真的。如果你能以某种方式使用群论来加速这个计数问题，那就太好了。但据我所知，这个问题的描述没有什么深刻之处。

最后，如果不是精确地计算低于阈值的排列数量，而是只想近似计算这个数字，那么游戏可能会完全改变。(您可以在多项式时间内近似永久数，但这在这里没有帮助。)我不得不考虑该怎么做；无论如何，这不是提出的问题。

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

但是，当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可以通过在列表endcachelist2中执行二进制搜索来更快地完成工作。(我刚从stackoverflow中了解到这是在Python的二等分模块中实现的，尽管性能代码无论如何都不会用Python编写。)与头缓存不同，即使list1和list2的条目之间没有数字上的重合，端缓存也可以大大提高代码的速度。Ryser的算法在没有数字重合的情况下对于这个问题也很糟糕，所以对于这种类型的输入，我只看到了两种加速:使用"all“测试和"none”测试来锯断搜索树的一个分支，以及end cache。

Answer 2

可能不是(没有简化的假设)：您的问题是NP难的。下面是对SUBSET-SUM的一个简单的简化。设count_perms(L1, L2, x)表示函数“计算L2的排列数，使得prodSum(L1，L2) < x”。

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

因此，如果有一种方法可以有效地计算函数count_perms(L1, L2, x)，那么我们就会有一个有效的算法来计算SUBSET_SUM(L2，n)。

Answer 3

看起来，如果l1和l2都被排序为高->低(或者低->高，不管怎么说，如果它们有相同的顺序)，结果是最大化的，如果它们是相反的排序，结果是最小化的，并且其他顺序的改变似乎遵循一些规则；在连续的整数列表中交换两个数字总是减少固定的数量，这似乎与它们之间的距离有关(即交换1和3或2和4具有相同的效果)。这只是一个小小的混乱，但想法是有一个最大值，最小值，如果它们之间有一些预先指定的值，那么就有方法计算使之成为可能的排列(尽管；如果列表不是均匀分布的，那么就没有。好吧，据我所知不是。如果l2是(1 2 4 5)交换1 2和2 4会有不同的效果)