logo标签列表

动态规划：乘积之和

algorithmstatisticsdynamic-programming
12

假设你有两个列表 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] 的整数列表，则无法解决此问题。 我仍然对假设这个约束条件的解决方案感兴趣。

你是在询问总和吗？还是在询问一个特定的值，其中prodSum(L1,L2) < X？ - DarthVader
不是作业。这实际上是一个问题，我需要解决以计算统计函数。我去掉了它的上下文，因为对于非统计学家来说，这会使问题变得不必要地复杂。 - dsimcha
你的意思是我们可以假设L1 = range（1，n）和L2 = range（1，m）吗？也就是说，它们都是某个点之前所有整数的列表？ - Managu
没错。只有在你假设这一点时，n才等于m，因为len(L1) == len(L2)。 - dsimcha
2
这实际上是为了计算Spearman's Rho（http://en.wikipedia.org/wiki/Spearman%27s_rho）的精确P值。对于固定的边缘分布（如果您的边缘是等级且没有关系），测试统计量是总乘积的简单函数。我没有在这里放置此上下文，因为大约99％的程序员可能从未听说过Spearman's Rho，我认为这只会让人们感到困惑。 - dsimcha
显示剩余2条评论
4个回答
9
我希望首先消除一些关于数学的混淆，然后讨论两个解决方案并给出其中一个的代码。
有一个称为#P的计数类，它非常像yes-no类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的列表上使用此算法，首先选择一个基数x，它是大于n阶乘的10或2的幂。现在制作矩阵

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

如果使用Ryser formula计算矩阵M的permanent，那么在基数为x的情况下，permanent的第k位数字告诉您点积恰好为k的排列数。此外，Ryser公式比直接对所有排列求和要快得多。(但它仍然是指数级的，因此它并不违反计算permanent是#P-hard的事实。)
另外，是的，排列集合是对称群。如果您能以某种方式使用群论加速这个计数问题，那就太好了。但据我所知，没有什么深刻的东西来自这个问题的描述。
最后，如果您只想近似计算低于阈值的排列数，那么游戏可能会完全改变。(您可以在多项式时间内近似计算permanent，但这在这里没有帮助。)我需要考虑该怎么做；在任何情况下，这都不是提出的问题。
我意识到以上讨论和代码中缺少另一种缓存/动态规划。代码中实现的缓存是早期缓存：如果只将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可以通过在列表endcache [list2]中进行二进制搜索来更快地完成工作。（我刚从stackoverflow了解到这在Python的bisect模块中实现，尽管性能代码无论如何都不会用Python编写。）与头缓存不同，即使在list1和list2的条目中没有数字巧合，end cache也可以大大加速代码。对于没有数字巧合的这种输入，Ryser算法也很糟糕，因此我只看到两个加速：使用“all”测试和“none”测试锯掉搜索树的一支，并使用end cache。
7

可能不行（没有简化假设的情况下）：你的问题是NP难的。以下是到子集和问题的简单归约。让count_perms(L1, L2, x)表示函数“计算L2的排列中乘积和L1的乘积小于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)。
注意 prodSum 是点积。令 N = len(L2)。那么 prodSum([1]*N, L2) == sum(L2)。由于加法是可交换的，如果 x > sum(L2)，则 count_perms(L1, L2, x) == N!，如果 x <= sum(L2)，则 count_perms(L1, L2, x) == 0。因此，count_perms(L1,L2,n)-count_perms(L1,L2,n-1) 要么是 N!，要么是 0。由于相当多的子集和不属于这两种形式，上述算法无法解决子集和问题。 - outis
很好的发现。让我们再添加一个循环（仍然是多项式时间约简）。 - Managu
2
这实际上是一个抽象代数问题。虽然对我来说有些久远，但以下是一些入手的方法。以下内容没有什么特别重要的（都非常基础；是每个群同构于置换群的扩展），但它提供了另一种看待这个问题的方式。
我将尝试遵循相当标准的符号： “x”是一个向量，“xi”是x的第i个分量。如果“L”是一个列表，则L是等效的向量。“1n”是一个所有分量= 1的向量。自然数ℕ的集合被认为是正整数。 “[a，b]”是从a到b（含）的整数集。 “θ（x，y）”是由x和y形成的角度。
请注意，prodSum是点积。问题等价于找到所有通过对L2进行操作（置换元素）生成的向量L，使得θ（L1，L）小于给定的角度α。该操作等效于通过具有演示的子空间反射ℕn中的点：

< ℕn | (xixj-1)(i,j) ∈ A >

其中i和j在[1，n]中，A至少有一个元素，并且没有（i，i）在A中（即A是[1，n] 2 的非反身子集，其中| A|> 0）。更明确地说（也更模糊），子空间是其中一个或多个分量等于另一个或多个分量的点。反射对应于其列均为标准基向量的矩阵。
让我们将反射群命名为“RPn”（它应该有另一个名称，但我记不起来了）。 RPn同构于对称群Sn。因此，

| RPn | = | Sn | = n！

在三维中，这给出了一个阶为6的群。反射群是D3，三角形对称群，作为立方体对称群的子群。事实证明，您还可以通过以π/3的增量围绕沿着1n的线旋转L2来生成点。这是模量组ℤ6，这指向一个可能的解决方案：找到一个顺序为n!的群，并使用最少数量的生成器来生成L2的排列，使其具有递增，然后递减的角度与L2。从那里，我们可以尝试直接生成元素L，其中θ（L1，L）<α（例如，我们可以在每个序列的前半部分上进行二进制搜索以找到转换点；有了这个，我们可以指定满足条件的其余序列并在O（1）时间内计数）。让我们将此组称为RP'n。
RP'4由4个同构于ℤ6的子空间构成。更一般地，RP'n由n个同构于RP'n-1的子空间构成。
这就是我的抽象代数知识真正开始失败的地方。我将尝试继续构建，但Managu的答案似乎没有什么希望。我担心将RP3缩减为ℤ6是我们唯一有用的缩减。
0

看起来，如果l1和l2都是按高->低（或低->高，如果它们具有相同的顺序）排序的，则结果最大化；如果它们按相反的顺序排序，则结果最小化，并且其他排序方式似乎遵循某些规则；在连续的整数列表中交换两个数字总是会将总和减少固定数量，这个数量似乎与它们之间的距离有关（例如，交换1和3或2和4具有相同的效果）。这只是一点小玩意儿，但是想法是存在一个最大值、一个最小值，如果某些预先指定的值介于它们之间，则有方法计算使其成为可能的排列（尽管；如果列表不均匀分布，则没有。好吧，至少我不知道。如果l2是（1 2 4 5），则交换1 2和2 4会产生不同的效果）

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接