用Python解决难题

Question

我得到了一个谜题并希望用Python解决。

谜题：

一个商人有一个40公斤的重物，他在自己的店里使用。 有一次，它从他手中掉落并被损坏成了4个部分。 但令人惊讶的是，现在他可以使用这4个部分组合出1公斤到40公斤之间的任何重量。

所以问题是，这4个部分的重量是多少？

现在我想用Python解决这个问题。

从谜题中唯一的约束条件是这4个部分的总和为40。根据这个条件，我可以筛选出所有总和为40的4个值的组合。

import itertools as it

weight = 40
full = range(1,41)
comb = [x for x in it.combinations(full,4) if sum(x)==40]

comb的长度为297。

现在我需要检查comb中每组值并尝试所有操作的组合。

例如，如果(a,b,c,d)是comb中的第一组值，则我需要检查a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........以此类推。

我尝试了很多次，但我被卡在这个阶段，即如何检查这些计算的所有组合到每组4个值中。

问题：

1）我想要获得所有可能的[a,b,c,d]和[+,-]组合的列表。

2）是否有更好的方法并告诉我如何从这里继续？

此外，我希望完全不借助任何外部库，只使用Python的标准库。

编辑：对不起，晚了点提供信息。它的答案是(1,3,9,27)，我几年前就找到了并且验证了答案。

编辑：目前，fraxel的答案与time = 0.16 ms完美地工作。更好、更快的方法总是受欢迎的。

谢谢,

ARK

- Abid Rahman K

---

这道谜题比你想的要棘手得多；我不确定你是否可以轻松地用蛮力破解它。诀窍在于，为了称量某些重量，他可能需要将一些物品加到天平的两侧。考虑一个简化版本：将一个 4 公斤的重物分成两个部分，可以测量任何高达 4 公斤的重量。答案是一个1公斤的物品和一个3公斤的物品。要测量2公斤，你必须把其中一个物品放在天平的每一侧。 - Jacob Mattison

@JacobM的建议是最好的：从一个更简单的问题开始，看看是否能找到一种模式，使你能够解决更复杂的问题。此外，请注意，除非你确定每个重量都是唯一的，否则组合将无法给你想要的结果。（为了看到这一点，请尝试将重量更改为10，将full更改为range（1,10）。更容易玩弄它的功能。） - Jeff Tratner

@ JacobM...当然可以。也就是说，你可以在天平的两侧放置不同的重量以达到所需的重量。比如我在问题中提到了“负号”，例如a-b, a-b+c-d ....。“减号”表示将重量放在另一侧天平上。我想我需要在问题中解释一下。感谢您的提醒。 - Abid Rahman K

读一下问题，安德鲁想用Python解决它，我们有什么理由阻止他呢！ - jgritty

好的，我删除了我的评论，以防它成为不必要的“剧透”（抱歉）。如果你想知道如何只写下答案，请给我发电子邮件。 - andrew cooke

Answer 1

之前的步骤说明：

我们知道对于所有在0到40之间的x，a*A + b*B + c*C + d*D = x，并且a, b, c, d限制为-1, 0, 1。 显然，A + B + C + D = 40。下一个情况是x = 39，因此最小的移动显然是删除一个元素（唯一可能导致成功平衡至39的移动）：

A + B + C = 39，因此D = 1。

接下来：

A + B + C - D = 38

接下来：

A + B + D = 37，因此C = 3

然后：

A + B = 36

然后：

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31， 因此A = 9

因此，B = 27

因此，这些重量分别为1, 3, 9, 27

实际上，这可以立即推断出它们必须都是3的倍数。

有趣的更新：

这里有一些Python代码，可以找到任何丢失重量的最小重量集，以跨越空间：

def find_weights(W):
    weights = []
    i = 0
    while sum(weights) < W:
        weights.append(3 ** i)
        i += 1
    weights.pop()
    weights.append(W - sum(weights))
    return weights

print find_weights(40)
#output:
[1, 3, 9, 27]

为了进一步说明这个解释，可以将问题看作是覆盖数字空间[0, 40]所需的最小重量数。显然，每个重量可以进行三元操作（加重、减重、移动到另一侧）。因此，如果我们将我们不知道的重量(A, B, C, D)按降序排列，我们的移动可以总结为：

    ABCD:   Ternary:
40: ++++     0000
39: +++0     0001
38: +++-     0002
37: ++0+     0010
36: ++00     0011
35: ++0-     0012
34: ++-+     0020
33: ++-0     0021
32: ++--     0022
31: +0++     0100
etc.

我已经列举了从0到9的三进制计数法，以说明我们实际上处于三进制数系统（基数为3）中。我们的解决方案始终可以写成：

3**0 + 3**1 +3**2 +...+ 3**N >= Weight

对于最小的N，这个结论始终成立。最小解法将始终采用此形式。

此外，我们可以轻松地解决大重量下的问题，并找到跨越空间所需的最小碎片数：

一个人丢了一个已知重量W的物品，它破成了若干块。他现在用这些碎片可以称量任何不超过W的重量。那么有多少种碎片，它们各自的重量是多少？

#what if the dropped weight was a million Kg:
print find_weights(1000000)
#output:
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 202839]

尝试使用排列组合方法处理大重量和未知数量的零件！

- fraxel

---

A + B + C = 39，因此D = 1，这是必然的。我对此并不确定。如果你有14和15的重量，你可以使用它们中的两个来得到1，一个放在每一边，因为15-14 = 1。所以不确定“必然性”是否是正确的词。 - jgritty

抱歉，我用了错误的代词，我的意思是那个从14和15开始的人会遇到问题。 - jgritty

@Abid Rahman K - 干杯，:) 我将提供一个非常有趣的更新，包括一些代码和更多解释。这是一个非常有趣的问题。使用这种方法可以轻松解决问题：`一个人扔下1000000公斤的重物，他的新重量允许他称量任何重量高达1000000公斤！它们是什么，有多少个？ - fraxel

好答案！这让我想起了这个漫画（http://calamitiesofnature.com/archive/?c=548）... - Jaime

@Jaime - 哈哈，那太荒谬了 :) - fraxel

Answer 2

这里是一个暴力的itertools解决方案：

import itertools as it

def merchant_puzzle(weight, pieces):
    full = range(1, weight+1)
    all_nums = set(full)
    comb = [x for x in it.combinations(full, pieces) if sum(x)==weight]
    funcs = (lambda x: 0, lambda x: x, lambda x: -x)
    for c in comb:
        sums = set()
        for fmap in it.product(funcs, repeat=pieces):
            s = sum(f(x) for x, f in zip(c, fmap))
            if s > 0:
                sums.add(s)
                if sums == all_nums:
                    return c

>>> merchant_puzzle(40, 4)
(1, 3, 9, 27)

如果想了解它如何工作，请查看Avaris提供的答案，这是相同算法的实现。

- Andrew Clark

---

哇！当我在写解释的时候，你已经编写了同样的东西 :)。 - Avaris

Answer 3

你很接近答案了 :).

由于这是一个你想解决的难题，我只会给出一些提示。对于这部分：

例如，如果(a,b,c,d)是comb中的第一个值集合，则我需要检查a、b、c、d、a+b、a-b、……a+b+c-d、a-b+c+d，以此类推。

考虑到：每个重量可以放在一个天平上，也可以放在另一个天平上，或者不放在任何一个天平上。因此，对于a的情况，可以表示为[a，-a，0]。其他三个同理。现在，您需要使用这3种可能性的所有可能组合（提示：itertools.product）来进行配对。然后，配对的一种可能测量（假设：(a，-b，c，0)）仅是这些数的总和（a-b+c+0）。

剩下的就是检查是否能够“测量”所有所需的重量。此处set可能会有帮助。

PS：正如评论中所述，对于一般情况，这些分裂的重量可能不需要是不同的（对于此问题是必要的）。您可能需要重新考虑itertools.combinations。

- Avaris

---

+1 - “这可以表示为[a，-a，0]”。我没有想到这个技巧。那一个简单的语句是转折点。谢谢。 - Abid Rahman K

Answer 4

我用暴力方法解决了第二部分。

如果您不想看答案，请不要单击此处。显然，如果我在排列组合方面更加熟练，这将需要更少的剪切/粘贴搜索/替换。

http://pastebin.com/4y2bHCVr

- jgritty

---

哦我的天，我简直无法相信你写了那么多行代码！！！它在“time = 0.185 s”的时间内正常工作。 - Abid Rahman K

Answer 5

我不懂Python语法，但也许你可以解码这段Scala代码；从第二个for循环开始：

def setTo40 (a: Int, b: Int, c: Int, d: Int) = {

val vec = for (
  fa <- List (0, 1, -1);
  fb <- List (0, 1, -1);
  fc <- List (0, 1, -1);
  fd <- List (0, 1, -1);
  prod = fa * a + fb * b + fc * c + fd * d;
  if (prod > 0)
  ) yield (prod)

  vec.toSet
}

for (a <- (1 to 9);
  b <- (a to 14);
  c <- (b to 20);
  d = 40-(a+b+c)
  if (d > 0)) { 
    if (setTo40 (a, b, c, d).size > 39)
      println (a + " " + b + " " + c + " " + d)
  }

- user unknown

Answer 6

使用重量[2, 5, 15, 18]，您也可以测量所有1至40公斤之间的物体，尽管其中一些需要间接测量。例如，要测量39公斤的物体，您首先会将其与40公斤进行比较，天平会倾向于40公斤一侧（因为39 < 40），但是如果您移除2公斤的重量，它会倾向于另一侧（因为39 > 38），从而您可以得出该物体重量为39公斤的结论。

更有趣的是，使用重量[2, 5, 15, 45]，您可以测量所有高达67公斤的物体。

- Luís Pureza

---

你好，谢谢你的回答。我的问题不是要找到答案，而是要通过编程来解决它，特别是使用Python。 - Abid Rahman K

没问题，但请注意编写一个程序来找到这个答案会稍微复杂一些，因为你必须考虑间接测量。 - Luís Pureza

Answer 7

我的解决方案如下：

    #!/usr/bin/env python3

weight = 40
parts = 4
part=[0] * parts

def test_solution(p, weight,show_result=False):
    cv=[0,0,0,0]
    for check_weight in range(1,weight+1):
        sum_ok = False
        for parts_used in range(2 ** parts):
            for options in range(2 ** parts):
                for pos in range(parts):
                    pos_neg = int('{0:0{1}b}'.format(options,parts)[pos]) * 2 - 1
                    use = int('{0:0{1}b}'.format(parts_used,parts)[pos])
                    cv[pos] = p[pos] * pos_neg * use
                if sum(cv) == check_weight:
                    if show_result:
                        print("{} = sum of:{}".format(check_weight, cv))
                    sum_ok = True
                    break
        if sum_ok:
            continue
        else:
            return False
    return True

for part[0] in range(1,weight-parts):
    for part[1] in range(part[0]+1, weight - part[0]):
        for part[2] in range( part[1] + 1 , weight - sum(part[0:2])):
            part[3] = weight - sum(part[0:3])
            if test_solution(part,weight):
                print(part)
                test_solution(part,weight,True)
                exit()

它为给定的权重提供了所有解决方案

- Jeromba6

Answer 8

比我之前的答案更加动态，因此它也适用于其他数字。但是将其分成5个部分需要一些时间：

#!/usr/bin/env python3

weight = 121
nr_of_parts = 5

# weight = 40
# nr_of_parts = 4

weight = 13
nr_of_parts = 3


part=[0] * nr_of_parts

def test_solution(p, weight,show_result=False):
    cv=[0] * nr_of_parts
    for check_weight in range(1,weight+1):
        sum_ok = False
        for nr_of_parts_used in range(2 ** nr_of_parts):
            for options in range(2 ** nr_of_parts):
                for pos in range(nr_of_parts):
                    pos_neg = int('{0:0{1}b}'.format(options,nr_of_parts)[pos]) * 2 - 1
                    use = int('{0:0{1}b}'.format(nr_of_parts_used,nr_of_parts)[pos])
                    cv[pos] = p[pos] * pos_neg * use
                if sum(cv) == check_weight:
                    if show_result:
                        print("{} = sum of:{}".format(check_weight, cv))
                    sum_ok = True
                    break
        if sum_ok:
            continue
        else:
            return False
    return True

def set_parts(part,position, nr_of_parts, weight):
    if position == 0:
        part[position] = 1
        part, valid = set_parts(part,position+1,nr_of_parts,weight)
        return part, valid
    if position == nr_of_parts - 1:
        part[position] = weight - sum(part)
        if part[position -1] >= part[position]:
            return part, False
        return part, True
    part[position]=max(part[position-1]+1,part[position])
    part, valid = set_parts(part, position + 1, nr_of_parts, weight)
    if not valid:
        part[position]=max(part[position-1]+1,part[position]+1)
        part=part[0:position+1] + [0] * (nr_of_parts - position - 1)
        part, valid = set_parts(part, position + 1, nr_of_parts, weight)
    return part, valid

while True:
    part, valid = set_parts(part, 0, nr_of_parts, weight)
    if not valid:
        print(part)
        print ('No solution posible')
        exit()
    if test_solution(part,weight):
        print(part,'    ')
        test_solution(part,weight,True)
        exit()
    else:
        print(part,'   ', end='\r')

- Jeromba6

Answer 9

如果有人不想导入库来导入组合/排列，这将生成所有可能的4步策略...

# generates permutations of repeated values
def permutationsWithRepeats(n, v):
    perms = []
    value = [0] * n
    N = n - 1
    i = n - 1

    while i > -1:
        perms.append(list(value))

        if value[N] < v:
            value[N] += 1
        else:
            while (i > -1) and (value[i] == v):
                value[i] = 0
                i -= 1

            if i > -1:
                value[i] += 1
                i = N

    return perms

# generates the all possible permutations of 4 ternary moves
def strategy():
    move = ['-', '0', '+']
    perms = permutationsWithRepeats(4, 2)

    for i in range(len(perms)):
        s = ''

        for j in range(4):
            s += move[perms[i][j]]

        print s

# execute
strategy()

- user3821369