algorithm - 不重复排列

Question

我想知道，解决这个问题的最佳方法是什么:

给定 x、y 和 y 整数:a1、a2、a3 .. 找到所有组合a1 ± a2 ± ... ± ay = x, y < 20.

我最近的做法是找到存储在表T中的1和0的所有排列，然后根据数字T[i]是否为1和0，从总和中加上或减去ai。问题是有n! n 元素数组的排列。因此，对于 20 个元素的数组，我必须检查 20!大多数重复的可能性。您能否建议我解决问题的任何可能方法？

Answer 1

只有 2^20(超过一百万)个长度为 20 的二进制向量，而不是不可行的 20!。使用应该能够在不到一秒的时间内暴力破解，特别是如果你使用 Gray Code这将允许您在一个步骤中从一个候选总和传递到另一个候选总和(例如，从 a + b - c -d 到 a + b - c + d只需添加 2*d。

如果 y 变得更大，@MikeWise 出色的分支定界思想将会很好。生成一个根节点为 0 的树。给它 -a1 和 +a1 的 child 。然后通过添加和减去 a2 等 4 个孙子。如果你从目标 x 中得到的距离超过剩余 ai 的总和 - - 你可以修剪那个分支。在最坏的情况下，这可能比基于格雷码的暴力破解略差(因为你需要在每个节点上做更多的处理)，但在最好的情况下，你可能能够排除大多数可能性。

On Edit:这是一些 Python 代码。首先，我定义了一个生成器，给定一个整数 n，它会连续返回需要翻转的位位置以逐步执行格雷码:

def grayBit(n):
    code = [0]*n
    odd = True
    done = False
    while not done:
        if odd:
            code[0] = 1 - code[0] #flip bit
            odd = False
            yield 0
        else:
            i = code.index(1)
            if i == n-1:
                done = True
            else:
                code[i+1] = 1 - code[i+1]
                odd = True
                yield i+1

(这使用了我多年前在 Stanton 和 White 的优秀著作“Constructive Combinatorics”中学到的算法)。

然后——我用它来返回所有解决方案(作为由输入数字列表组成的列表，根据需要插入负号)。关键是我可以将当​​前位翻转并加或减两倍相应的数字:

def signedSums(nums, target):
    n = len(nums)
    patterns = []
    total = sum(nums)
    pattern = [1]*n
    if target == total: patterns.append([x*y for x,y in zip(nums,pattern)])
    deltas = [2*i for i in nums]
    for i in grayBit(n):
        if pattern[i] == 1:
            total -= deltas[i]
        else:
            total += deltas[i]
        pattern[i] = -1 * pattern[i]
        if target == total: patterns.append([x*y for x,y in zip(nums,pattern)])
    return patterns

典型输出:

>>> signedSums([1,2,3,4,5,9],6)
[[1, -2, -3, -4, 5, 9], [1, 2, 3, -4, -5, 9], [-1, 2, -3, 4, -5, 9], [1, 2, 3, 4, 5, -9]]

评估只需要一秒钟:

>>> len(signedSums([i for i in range(1,21)],100))
2865

因此，有 2865 种方法可以对 1,2,..,20 范围内的整数进行加减运算，得到净和 100。

我假设 a1 可以被添加或减去(而不是仅仅添加，如果从字面上看，这就是你的问题所暗示的)。请注意，如果你真的想坚持 a1 出现积极，那么你可以从 x 中减去它并将上述算法应用于列表的其余部分和调整后的目标.

最后，不难看出，如果你解决 subset sub problem具有一组权重 {2*a1, 2*a2, 2*a3, .... 2*ay} 并且目标总和为 x + a1 + a2 + .. . + ay 然后所选的子集将与原始问题的解决方案中出现正号的子集完全对应。因此，您的问题很容易简化为子集和问题，因此确定它是否有任何解决方案是 NP 完全的(并且 NP 难以列出所有解决方案)。