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] 的整数列表，这是不可能的。我仍然会对假设这种约束的解决方案感兴趣。

4

4 回答 4

9

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

有一个称为#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，它是大于 n 阶乘的 10 或 2 的幂。现在制作矩阵

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

如果您使用Ryser 公式计算此矩阵 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 足够短，countprods 可以通过在列表 endcache[list2] 中进行二进制搜索来更快地完成它的工作。（我刚刚从 stackoverflow 了解到，这是在 Python 的 bisect 模块中实现的，尽管性能代码无论如何都不会用 Python 编写。）与头部缓存不同，末端缓存可以大大加快代码速度，即使有list1 和 list2 的条目之间没有数字重合。Ryser 的算法在没有数值巧合的情况下也很讨厌这个问题，所以对于这种类型的输入，我只看到两个加速度：

于 2009-12-05T23:30:02.393 回答
7

可能不是（没有简化假设）：您的问题是 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)。

于 2009-11-29T03:10:56.603 回答
2

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

我会尽量坚持相当标准的符号：“ x ”是一个向量，“ x i ”是 x 的第i个分量。如果“L”是一个列表，则L是等效向量。“ 1 n ” 是一个所有分量 = 1 的向量。自然数集 ℕ 被视为正整数。"[a,b]" 是从 a 到 b 的整数集合，包括在内。"θ( x , y )" 是x和y形成的角度

注意prodSum是点积。这个问题等价于找到由 L2 上的操作（置换元素）生成的所有向量L，使得 θ( L1 , L ) 小于给定角度 α。该操作相当于通过具有表示的子空间反映 ℕ<sup>n 中的一个点：

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

其中 i 和 j 在 [1,n] 中，A至少有一个元素，并且没有 (i,i) 在其中A（即是 [1,n] 2A的非自反子集，其中 | | > 0）。说得更清楚（也更模糊），子空间是一个或多个分量等于一个或多个其他分量的点。反射对应于其列都是标准基向量的矩阵。A

让我们将反射组命名为“RP n ”（它应该有另一个名称，但记忆失败）。RP n同构于对称群 S n。因此

|RP n | = |S n | = n！

在 3 维中，这给出了一个 6 阶群。反射群是 D 3，三角形对称群，作为立方体对称群的子群。事实证明，您还可以通过围绕沿1 n的线以 π/3 的增量旋转L2来生成点。这是模群 ℤ<sub>6，这指向了一个可能的解决方案：找到一个 n 阶群！使用最少数量的生成器，并使用它来生成 L2 的排列，作为与L2的角度增加然后减小的序列。从那里，我们可以尝试用θ( L1 , L) < α 直接（例如，我们可以对每个序列的前半部分进行 binsearch 以找到转换点；这样，我们可以指定满足条件的序列的其余部分并在 O(1) 时间内对其进行计数）。我们称这个组为 RP' n。

RP' 4由与 ℤ<sub>6 同构的 4 个子空间构成。更一般地，RP' n由与 RP' n-1同构的 n 个子空间构成。

这就是我的抽象代数肌肉真正开始失效的地方。我会继续努力建设，但 Managu 的回答并没有留下太多希望。我担心将 RP 3降低到 ℤ<sub>6 是我们可以做出的唯一有用的降低。

于 2009-12-02T03:34:19.073 回答
0

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

于 2009-11-29T03:57:44.540 回答