动态规划：加总产品

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的列表，首先选择一个基本x，它是10或2的幂乘以n的因子。现在让矩阵

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

如果计算永久使用Ryser formula这个矩阵M，那么永久的底数x的第k个数字告诉你排列为其积正是数k。此外，Ryser公式比直接对所有排列进行求和要快得多。 （但它仍然是指数型的，所以它不会与计算永久物是＃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足够短，则通过在列表endcache [list2]中执行二进制搜索，countprods可以更快地完成工作。 （我刚刚从stackoverflow得知，这是在Python中的bisect模块中实现的，尽管性能代码不会用Python编写）。与头缓存不同，最终缓存可以加快代码速度，即使存在在list1和list2的条目中没有数字符合。 Ryser的算法对于这个问题也没有数值上的一致性，所以对于这种类型的输入，我只能看到两种加速度：使用“全部”测试和“无”测试以及结束缓存锯掉搜索树的一个分支。

Answer 2

可能不是（没有简化的假设）：你的问题是NP-Hard。这是一个微不足道的减少到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具有相同的效果）。这只是一个小小的混乱，但想法是有一个最大值，一个最小值，如果它们之间有某个预先指定的值，就有办法对这种可能的排列进行计数（虽然; if如果l2是（1 2 4 5）交换1 2和2 4会产生不同的效果）

Answer 4

这也可以看出，成为一个抽象代数问题。对我来说已经有一段时间了，但是这里有几件事要开始。关于以下内容（这一切都非常基本;扩展了每个组与同一个排列组同构的事实），但它提供了一种查看问题的不同方式。

我会尽力坚持相当标准的符号：“X”是一个载体，而“X_我”是X的我^个组件。如果“L”是列表，则L是等效向量。 “ ⁿ”是所有分量= 1的向量。自然数集合ℕ被视为正整数。 “[a，b]”是从a到b的整数集合。 “θ（X，ÿ）” 是由X和形成的角度γ

注prodSum是点积。这个问题相当于找到由L2上的操作（置换元素）产生的所有向量，使得θ小于给定角度α（θ= 0°，θ= 0°，θ= 0°，θ= 0°，θ= 0°，θ= 0°，θ= 0°，θ= 30°）。该操作相当于反映ℕ^Ñ一个点通过子空间演示：

<ℕ^Ñ | （X_我X_Ĵ^-1）_{（I，J）∈A}>

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

让我们来命名反射组“RP _n”（它应该有另一个名称，但内存失败）。 RP _n与对称组S _n同构。因此

| RP _ñ | = | S _n | = n！

在3个维度，这给出了一个组的顺序6.反射基是d ，三角形对称群，如立方体对称组的子组。事实证明，您还可以通过围绕沿线 ⁿ以π/ 3为增量旋转L2来生成点。这是模块化组ℤ这指出了一个可能的解决方案：找到一组命令n！使用最少数量的生成器并使用该生成器生成L2的排列，随着序列的增加，然后递减，与L2的角度。从那里，我们可以尝试生成的元素大号与θ（L1，大号）<α直接（例如，我们可以在每个序列找到转变点的第一半BINSEARCH;条件是，我们可以指定满足条件的其余序列并在O（1）时间内进行计数）。我们称这组RP为' _n。

RP'由4个子空间构成，其与4个子空间同构，其与同构。更一般地，RP' _n由与n'同构的n个子空间构成' _n-1。

这是我的抽象代数肌肉真正开始失败的地方。我会尽力继续努力，但马那古的答案并没有留下太多希望。我担心减少RP 到ℤ是我们可以做的唯一有用的减少。