不重复排列

permutations without repetition

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

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

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

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

如果 y 变得更大,@MikeWise 出色的分支定界思想会很好。生成以 0 的根节点开始的树。给它 -a1+a1 的 children。然后通过加减 a2 等 4 grand children。如果你从目标 x 得到的总和比剩余 ai 的总和更远 - 你可以修剪它分支。在最坏的情况下,这可能比基于 Gray-code 的蛮力略差(因为您需要在每个节点上执行更多的处理),但在最好的情况下,您可能能够排除大多数可能性。

关于编辑:这是一些 Python 代码。首先,我定义了一个生成器,给定一个整数 n,连续 returns 哪个位位置需要翻转以逐步通过格雷码:

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" 中学到的算法)。

然后——我将其用于 return 所有解决方案(作为由输入数字列表组成的列表,根据需要插入负号)。关键是我可以取当前的 bit-to-flip 并加上或减去相应数字的两倍:

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 中减去它并将上述算法应用于列表的其余部分和调整后的目标。

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

我们有条件:

a1 ± a2 ± ... ± ay = x, y<20   [1]

首先,我会概括条件 [1],允许包括 'a1' 在内的所有 'a' 为 ±:

±a1 ± a2 ± ... ± ay = x   [2]

如果我们有 [2] 的解决方案,我们可以轻松获得 [1]

的解决方案

要解决[2]我们可以使用以下方法:

combinations list x 
    | x == 0 && null list = [[]]
    | null list = []
    | otherwise = plusCombinations ++ minusCombinations where
    a = head list
    rest = tail list
    plusCombinations = map (\c -> a:c) $ combinations rest (x-a)
    minusCombinations = map (\c -> -a:c) $ combinations rest (x+a)

解释:

  1. 第一个条件检查 x 是否达到零并使用列表中的所有数字。这意味着找到了解决方案,我们 return 单一解决方案:[[]]

  2. 第二个条件检查列表是否为空并且 x 不为 0 这意味着找不到解决方案,returning 空解决方案:[]

  3. 第三个分支意味着我们可以有两种选择:将 ai 与“+”或“-”一起使用,因此我们连接加号和减号组合

示例输出:

*Main> combinations [1,2,3,4] 2
[[1,2,3,-4],[-1,2,-3,4]]
*Main> combinations [1,2,3,4] 3
[]
*Main> combinations [1,2,3,4] 4
[[1,2,-3,4],[-1,-2,3,4]]