代码之家 › 专栏 › 技术社区 › 5rod

编写python程序来解决特定问题?

set math python

-2

5rod · 技术社区 · 2 年前

请考虑以下问题:

有多少种方法可以将整数1到14拆分为7对,以便在每对中,较大的数字至少是较小数字的2倍?

这显然是一个数学问题,有几种解决方案。我想知道是否有办法写一个python程序,自动搜索所有可能的对,并给我正确的答案。现在我要澄清一下:我不想要这个问题的“合理”解决方案,我想要一个python程序来解决它(通过所有可能的对)。

在研究如何做到这一点的可能性时,我考虑使用 set ,因为集合的顺序无关紧要。例如,如果我有一个for循环,它计算了所有的对,程序需要知道何时停止计算对,或者何时已经计算了某一对。由于for循环会有随机排序的对,如果我把这些对放在一个集合中,很可能会更容易弄清楚我是否已经计算过那对,因为顺序在集合中并不重要。

我现在有点困了。。。所以我愿意接受任何关于如何在这个想法或任何其他潜在想法的基础上构建的建议(我还没有任何代码要展示……希望很快就会出现)。

2 回复 | 直到 2 年前

Gaberocksall 2 年前

首先,我们需要了解这个问题。有很多方法可以将数字1到14配对,例如:

(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14) (一对符合标准)
(1, 14), (2, 13), (3, 12), (4, 11), (5, 10), (6, 9), (7, 8) (五对符合标准)
(1, 8), (2, 9), (3, 10), (4, 11), (5, 12), (6, 13), (7, 14) (所有配对都符合标准)

当我手工制作这些配对时,我首先选择一个数字进行配对 1 ,然后我选择一个数字进行配对 2 除非两个已经配对 1. 在哪种情况下,我选择一对 3 。该模式一直持续到所有数字配对为止。

让我们在python中递归地实现它:

def generate_pairings(unpicked_numbers, picked_pairs = ()):
    if not unpicked_numbers:
        # all of the numbers have been picked, and the pairs are finalized
        yield picked_pairs
        return

    # the pairing is incomplete - there are more numbers to pair up
    # go through every possible pairing and yield that
    for i in range(1, len(unpicked_numbers)):
        new_pair = (unpicked_numbers[0], unpicked_numbers[i])
        new_unpicked_numbers = unpicked_numbers[1:i] + unpicked_numbers[i+1:]

        yield from generate_pairings(new_unpicked_numbers, picked_pairs + (new_pair,))

然后,我们实现一个功能来检查某个配对是否符合您的标准:

def all_pairs_max_double_min(pairs):
    return all(max(pair) >= 2 * min(pair) for pair in pairs)

最后,我们简单地循环所有的组合&单独检查。

numbers = tuple(range(1, 15))
count = 0
for pairing in generate_pairings(numbers):
    if all_pairs_max_double_min(pairing):
        count += 1

print(f"There are {count} combinations in which all pairs' larger value is at least double the smaller value.")

有 144 所有对的较大值至少是较小值的两倍的组合。

blhsing 2 年前

您可以从一个所有数字的池开始,然后在每次递归调用中迭代地从中删除一对合法的数字,直到池为空,此时您已经找到了一个合法的数字对列表供输出:

def get_pairs(n, pool=None):
    if pool is None:
        pool = set(range(1, n + 1))
    if not pool:
        yield []
    for i in pool:
        for i2 in pool.intersection(range(i * 2, n + 1)):
            for pairs in get_pairs(n, pool - {i, i2}):
                yield [(i, i2)] + pairs

以便:

print(*get_pairs(6), sep='\n')

输出:

[(1, 4), (2, 5), (3, 6)]
[(1, 4), (3, 6), (2, 5)]
[(1, 5), (2, 4), (3, 6)]
[(1, 5), (3, 6), (2, 4)]
[(2, 4), (1, 5), (3, 6)]
[(2, 4), (3, 6), (1, 5)]
[(2, 5), (1, 4), (3, 6)]
[(2, 5), (3, 6), (1, 4)]
[(3, 6), (1, 4), (2, 5)]
[(3, 6), (1, 5), (2, 4)]
[(3, 6), (2, 4), (1, 5)]
[(3, 6), (2, 5), (1, 4)]

演示: https://ideone.com/Ut7j68