计算在约束下将整数 1-14 配对的方法数量

问题描述 投票：0回答：2

考虑以下问题：

有多少种方法可以将整数 1 到 14 分成 7 对，使得每对中较大的数字至少是较小的数字的 2 倍？

这显然是一道数学题，有多种解法。我想知道是否有一种方法可以编写一个 python 程序来自动搜索所有可能的对，并给我正确的答案。现在我要花点时间澄清一下：我不需要一个“合理”的解决方案来解决这个问题，我想要一个 python 程序来解决它（遍历所有可能的对）。

在考虑如何做到这一点的可能性时，我考虑使用 

set
，因为集合的顺序并不重要。例如，如果我有一个计算所有对的 for 循环，则程序需要知道何时停止对对进行计数或何时已经对某个对进行计数。由于 for 循环会有随机排序的对，如果我将这些对放入一个集合中，可能会更容易弄清楚我是否已经计算过该对，因为集合中的顺序并不重要。

我现在有点陷入困境......所以我愿意接受任何关于如何构建这个想法的建议，或任何其他潜在的想法（我还没有任何代码可以展示......希望能够到来很快）。

更新：

已解决。似乎有几种方法可以做到这一点，我构建了一些有效的代码（也使用了一些有用的答案）。

python math set combinations
2个回答
0
投票

首先我们需要了解问题。有很多方法可以将数字 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 组合，其中所有对的较大值至少是较小值的两倍。

0
投票

您可以从所有数字的池开始，然后在每次递归调用中迭代地从中删除合法的数字对，直到池为空，此时您已经找到了一组合法的数字对进行输出。将输出存储在一组冻结集中，以删除以不同顺序生成的重复组对：

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

这样：

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

将输出 144 个冻结的元组集合：

frozenset({(6, 12), (3, 13), (4, 10), (5, 11), (2, 8), (1, 9), (7, 14)})
frozenset({(2, 9), (4, 10), (6, 13), (7, 14), (1, 8), (5, 12), (3, 11)})
frozenset({(6, 12), (2, 8), (7, 14), (1, 11), (4, 9), (3, 10), (5, 13)})
frozenset({(3, 8), (6, 13), (1, 11), (4, 9), (2, 10), (5, 12), (7, 14)})
frozenset({(6, 13), (5, 11), (4, 8), (3, 12), (2, 10), (1, 9), (7, 14)})
frozenset({(1, 12), (5, 10), (6, 13), (2, 8), (7, 14), (4, 9), (3, 11)})
frozenset({(1, 12), (5, 10), (6, 13), (3, 9), (2, 8), (4, 11), (7, 14)})
frozenset({(6, 12), (4, 10), (3, 9), (7, 14), (1, 8), (2, 11), (5, 13)})
frozenset({(2, 9), (6, 13), (1, 10), (4, 8), (7, 14), (5, 12), (3, 11)})
frozenset({(6, 12), (2, 9), (4, 10), (1, 13), (3, 8), (5, 11), (7, 14)})
frozenset({(1, 12), (2, 9), (5, 10), (6, 13), (4, 8), (7, 14), (3, 11)})
frozenset({(6, 12), (3, 8), (5, 11), (1, 10), (4, 9), (2, 13), (7, 14)})
frozenset({(6, 12), (3, 8), (5, 10), (4, 11), (1, 9), (2, 13), (7, 14)})
frozenset({(6, 12), (2, 9), (4, 10), (5, 13), (7, 14), (1, 8), (3, 11)})
frozenset({(6, 12), (3, 8), (7, 14), (1, 11), (4, 9), (2, 10), (5, 13)})
frozenset({(6, 13), (5, 12), (2, 8), (1, 11), (4, 9), (3, 10), (7, 14)})
frozenset({(6, 12), (2, 9), (3, 8), (1, 13), (5, 10), (4, 11), (7, 14)})
frozenset({(6, 13), (3, 9), (4, 8), (1, 11), (2, 10), (5, 12), (7, 14)})
frozenset({(6, 12), (3, 13), (5, 10), (4, 9), (1, 8), (2, 11), (7, 14)})
frozenset({(2, 9), (4, 10), (6, 13), (5, 11), (3, 12), (1, 8), (7, 14)})
frozenset({(6, 12), (5, 10), (3, 9), (4, 13), (1, 8), (2, 11), (7, 14)})
frozenset({(1, 12), (2, 9), (3, 8), (5, 10), (6, 13), (4, 11), (7, 14)})
frozenset({(6, 12), (2, 9), (1, 13), (5, 11), (4, 8), (3, 10), (7, 14)})
frozenset({(3, 8), (5, 10), (6, 13), (2, 12), (1, 11), (4, 9), (7, 14)})
frozenset({(6, 12), (3, 13), (5, 10), (2, 8), (4, 11), (1, 9), (7, 14)})
frozenset({(2, 9), (3, 8), (6, 13), (1, 10), (4, 11), (5, 12), (7, 14)})
frozenset({(6, 13), (5, 12), (4, 8), (3, 10), (2, 11), (1, 9), (7, 14)})
frozenset({(2, 9), (3, 8), (5, 10), (6, 13), (1, 11), (4, 12), (7, 14)})
frozenset({(6, 12), (3, 8), (5, 10), (1, 11), (4, 9), (2, 13), (7, 14)})
frozenset({(2, 9), (6, 13), (5, 12), (4, 11), (1, 8), (3, 10), (7, 14)})
frozenset({(6, 12), (5, 13), (7, 14), (4, 9), (2, 10), (1, 8), (3, 11)})
frozenset({(1, 12), (2, 9), (4, 10), (3, 8), (6, 13), (5, 11), (7, 14)})
frozenset({(6, 12), (5, 11), (4, 8), (3, 10), (1, 9), (2, 13), (7, 14)})
frozenset({(6, 12), (5, 10), (1, 13), (3, 9), (2, 8), (4, 11), (7, 14)})
frozenset({(6, 12), (5, 13), (4, 8), (3, 11), (2, 10), (1, 9), (7, 14)})
frozenset({(6, 12), (2, 9), (5, 10), (4, 13), (7, 14), (1, 8), (3, 11)})
frozenset({(2, 9), (5, 10), (6, 13), (7, 14), (1, 8), (4, 12), (3, 11)})
frozenset({(6, 12), (4, 10), (3, 9), (5, 11), (1, 8), (2, 13), (7, 14)})
frozenset({(3, 8), (5, 10), (6, 13), (2, 12), (4, 11), (1, 9), (7, 14)})
frozenset({(6, 12), (5, 10), (2, 8), (4, 13), (7, 14), (1, 9), (3, 11)})
frozenset({(6, 12), (4, 8), (3, 10), (7, 14), (2, 11), (1, 9), (5, 13)})
frozenset({(5, 10), (6, 13), (2, 8), (7, 14), (4, 12), (1, 9), (3, 11)})
frozenset({(6, 12), (3, 9), (5, 11), (1, 10), (4, 13), (2, 8), (7, 14)})
frozenset({(6, 12), (3, 13), (5, 10), (2, 8), (1, 11), (4, 9), (7, 14)})
frozenset({(6, 12), (3, 9), (2, 8), (1, 10), (7, 14), (4, 11), (5, 13)})
frozenset({(6, 12), (5, 11), (4, 9), (1, 8), (3, 10), (2, 13), (7, 14)})
frozenset({(5, 10), (6, 13), (2, 8), (1, 11), (4, 9), (3, 12), (7, 14)})
frozenset({(6, 12), (5, 10), (3, 9), (4, 8), (1, 11), (2, 13), (7, 14)})
frozenset({(4, 10), (6, 13), (3, 9), (1, 8), (2, 11), (5, 12), (7, 14)})
frozenset({(6, 12), (5, 10), (4, 8), (7, 14), (1, 9), (2, 13), (3, 11)})
frozenset({(1, 12), (4, 10), (6, 13), (3, 9), (5, 11), (2, 8), (7, 14)})
frozenset({(3, 8), (5, 10), (6, 13), (2, 11), (4, 12), (1, 9), (7, 14)})
frozenset({(2, 9), (6, 13), (5, 12), (4, 8), (1, 11), (3, 10), (7, 14)})
frozenset({(6, 12), (3, 9), (7, 14), (4, 11), (1, 8), (2, 10), (5, 13)})
frozenset({(2, 9), (5, 10), (6, 13), (4, 8), (1, 11), (3, 12), (7, 14)})
frozenset({(6, 12), (3, 13), (5, 10), (4, 8), (2, 11), (1, 9), (7, 14)})
frozenset({(6, 12), (2, 9), (3, 13), (5, 10), (4, 11), (1, 8), (7, 14)})
frozenset({(5, 10), (6, 13), (2, 12), (4, 8), (7, 14), (1, 9), (3, 11)})
frozenset({(5, 10), (6, 13), (4, 8), (3, 12), (2, 11), (1, 9), (7, 14)})
frozenset({(6, 13), (3, 9), (2, 12), (1, 10), (5, 11), (4, 8), (7, 14)})
frozenset({(6, 13), (5, 11), (2, 12), (4, 9), (1, 8), (3, 10), (7, 14)})
frozenset({(6, 13), (5, 12), (3, 9), (4, 11), (1, 8), (2, 10), (7, 14)})
frozenset({(6, 12), (5, 10), (3, 9), (4, 11), (1, 8), (2, 13), (7, 14)})
frozenset({(4, 10), (3, 8), (6, 13), (5, 11), (2, 12), (1, 9), (7, 14)})
frozenset({(6, 13), (5, 11), (2, 8), (3, 10), (4, 12), (1, 9), (7, 14)})
frozenset({(4, 10), (6, 13), (3, 9), (2, 8), (1, 11), (5, 12), (7, 14)})
frozenset({(6, 13), (3, 9), (5, 11), (1, 10), (2, 8), (4, 12), (7, 14)})
frozenset({(6, 12), (2, 8), (1, 10), (3, 11), (4, 9), (7, 14), (5, 13)})
frozenset({(1, 12), (2, 9), (6, 13), (5, 11), (4, 8), (3, 10), (7, 14)})
frozenset({(2, 9), (6, 13), (5, 11), (1, 8), (4, 12), (3, 10), (7, 14)})
frozenset({(5, 10), (6, 13), (3, 12), (4, 9), (1, 8), (2, 11), (7, 14)})
frozenset({(6, 13), (5, 12), (4, 9), (1, 8), (2, 11), (3, 10), (7, 14)})
frozenset({(5, 10), (6, 13), (2, 8), (3, 12), (4, 11), (1, 9), (7, 14)})
frozenset({(6, 12), (3, 13), (5, 11), (2, 8), (1, 10), (4, 9), (7, 14)})
frozenset({(5, 10), (6, 13), (3, 9), (2, 8), (1, 11), (4, 12), (7, 14)})
frozenset({(6, 12), (3, 8), (5, 11), (4, 13), (2, 10), (1, 9), (7, 14)})
frozenset({(3, 8), (6, 13), (5, 11), (2, 10), (4, 12), (1, 9), (7, 14)})
frozenset({(6, 13), (2, 8), (1, 10), (7, 14), (4, 9), (5, 12), (3, 11)})
frozenset({(6, 12), (2, 9), (3, 8), (5, 10), (4, 13), (1, 11), (7, 14)})
frozenset({(6, 12), (4, 10), (3, 9), (2, 8), (7, 14), (1, 11), (5, 13)})
frozenset({(6, 12), (2, 9), (5, 10), (1, 13), (4, 8), (7, 14), (3, 11)})
frozenset({(4, 10), (6, 13), (5, 11), (2, 8), (3, 12), (1, 9), (7, 14)})
frozenset({(6, 12), (4, 10), (3, 8), (7, 14), (2, 11), (1, 9), (5, 13)})
frozenset({(6, 12), (3, 13), (5, 11), (4, 8), (2, 10), (1, 9), (7, 14)})
frozenset({(6, 12), (5, 10), (1, 13), (2, 8), (7, 14), (4, 9), (3, 11)})
frozenset({(5, 10), (6, 13), (3, 9), (2, 12), (4, 8), (1, 11), (7, 14)})
frozenset({(6, 12), (5, 10), (7, 14), (4, 9), (1, 8), (2, 13), (3, 11)})
frozenset({(6, 12), (2, 9), (3, 8), (5, 11), (4, 13), (1, 10), (7, 14)})
frozenset({(6, 12), (2, 9), (3, 8), (1, 10), (7, 14), (4, 11), (5, 13)})
frozenset({(6, 12), (5, 11), (4, 13), (3, 10), (2, 8), (1, 9), (7, 14)})
frozenset({(6, 12), (3, 9), (1, 10), (4, 8), (7, 14), (2, 11), (5, 13)})
frozenset({(5, 10), (6, 13), (3, 9), (2, 12), (4, 11), (1, 8), (7, 14)})
frozenset({(2, 9), (6, 13), (5, 11), (1, 10), (4, 8), (3, 12), (7, 14)})
frozenset({(6, 12), (1, 13), (3, 9), (5, 11), (4, 8), (2, 10), (7, 14)})
frozenset({(6, 12), (2, 9), (5, 11), (4, 13), (1, 8), (3, 10), (7, 14)})
frozenset({(6, 12), (5, 10), (1, 13), (3, 9), (4, 8), (2, 11), (7, 14)})
frozenset({(4, 10), (3, 8), (6, 13), (5, 12), (2, 11), (1, 9), (7, 14)})
frozenset({(6, 13), (5, 11), (2, 12), (4, 8), (3, 10), (1, 9), (7, 14)})
frozenset({(6, 13), (5, 11), (2, 8), (1, 10), (3, 12), (4, 9), (7, 14)})
frozenset({(6, 12), (3, 8), (5, 10), (4, 13), (2, 11), (1, 9), (7, 14)})
frozenset({(6, 12), (3, 8), (1, 10), (7, 14), (4, 9), (2, 11), (5, 13)})
frozenset({(5, 10), (6, 13), (3, 9), (1, 8), (4, 12), (2, 11), (7, 14)})
frozenset({(1, 12), (6, 13), (5, 11), (2, 8), (4, 9), (3, 10), (7, 14)})
frozenset({(6, 13), (3, 9), (1, 10), (4, 8), (2, 11), (5, 12), (7, 14)})
frozenset({(6, 12), (3, 8), (1, 13), (5, 10), (4, 9), (2, 11), (7, 14)})
frozenset({(6, 13), (3, 9), (2, 8), (1, 10), (4, 11), (5, 12), (7, 14)})
frozenset({(6, 12), (7, 14), (4, 9), (1, 8), (2, 11), (3, 10), (5, 13)})
frozenset({(6, 12), (3, 8), (1, 13), (5, 11), (4, 9), (2, 10), (7, 14)})
frozenset({(2, 9), (5, 10), (6, 13), (3, 12), (4, 11), (1, 8), (7, 14)})
frozenset({(6, 12), (3, 9), (4, 8), (7, 14), (1, 11), (2, 10), (5, 13)})
frozenset({(6, 12), (2, 9), (4, 8), (7, 14), (1, 11), (3, 10), (5, 13)})
frozenset({(3, 8), (6, 13), (1, 10), (4, 9), (2, 11), (5, 12), (7, 14)})
frozenset({(1, 12), (3, 8), (6, 13), (5, 11), (4, 9), (2, 10), (7, 14)})
frozenset({(6, 12), (2, 8), (3, 10), (7, 14), (4, 11), (1, 9), (5, 13)})
frozenset({(6, 12), (4, 10), (2, 8), (3, 11), (7, 14), (1, 9), (5, 13)})
frozenset({(2, 9), (4, 10), (3, 8), (6, 13), (1, 11), (5, 12), (7, 14)})
frozenset({(2, 9), (3, 8), (6, 13), (5, 11), (1, 10), (4, 12), (7, 14)})
frozenset({(3, 8), (6, 13), (5, 12), (2, 10), (4, 11), (1, 9), (7, 14)})
frozenset({(6, 13), (7, 14), (4, 9), (2, 10), (1, 8), (5, 12), (3, 11)})
frozenset({(4, 10), (6, 13), (3, 9), (2, 12), (5, 11), (1, 8), (7, 14)})
frozenset({(1, 12), (3, 8), (5, 10), (6, 13), (4, 9), (2, 11), (7, 14)})
frozenset({(6, 12), (2, 9), (7, 14), (4, 11), (1, 8), (3, 10), (5, 13)})
frozenset({(6, 12), (4, 10), (3, 8), (5, 11), (1, 9), (2, 13), (7, 14)})
frozenset({(6, 12), (3, 13), (5, 11), (4, 9), (2, 10), (1, 8), (7, 14)})
frozenset({(5, 10), (6, 13), (2, 12), (7, 14), (4, 9), (1, 8), (3, 11)})
frozenset({(3, 8), (6, 13), (5, 11), (2, 12), (1, 10), (4, 9), (7, 14)})
frozenset({(6, 12), (1, 13), (5, 11), (2, 8), (4, 9), (3, 10), (7, 14)})
frozenset({(6, 12), (2, 9), (3, 13), (5, 11), (1, 10), (4, 8), (7, 14)})
frozenset({(6, 13), (5, 11), (3, 12), (4, 9), (2, 10), (1, 8), (7, 14)})
frozenset({(6, 12), (4, 10), (1, 13), (3, 9), (5, 11), (2, 8), (7, 14)})
frozenset({(6, 12), (2, 9), (3, 13), (5, 10), (4, 8), (1, 11), (7, 14)})
frozenset({(6, 12), (2, 9), (5, 13), (1, 10), (4, 8), (3, 11), (7, 14)})
frozenset({(6, 12), (3, 9), (5, 11), (1, 10), (4, 8), (2, 13), (7, 14)})
frozenset({(6, 13), (5, 12), (4, 8), (7, 14), (2, 10), (1, 9), (3, 11)})
frozenset({(1, 12), (5, 10), (6, 13), (3, 9), (4, 8), (2, 11), (7, 14)})
frozenset({(6, 12), (3, 8), (2, 10), (7, 14), (4, 11), (1, 9), (5, 13)})
frozenset({(6, 12), (5, 10), (3, 9), (4, 13), (2, 8), (1, 11), (7, 14)})
frozenset({(6, 12), (2, 9), (3, 13), (4, 10), (5, 11), (1, 8), (7, 14)})
frozenset({(4, 10), (6, 13), (5, 12), (2, 8), (7, 14), (1, 9), (3, 11)})
frozenset({(6, 13), (5, 12), (2, 8), (3, 10), (4, 11), (1, 9), (7, 14)})
frozenset({(6, 12), (2, 9), (4, 10), (3, 8), (7, 14), (1, 11), (5, 13)})
frozenset({(1, 12), (6, 13), (3, 9), (5, 11), (4, 8), (2, 10), (7, 14)})
frozenset({(6, 12), (3, 9), (5, 11), (4, 13), (2, 10), (1, 8), (7, 14)})
frozenset({(6, 13), (3, 9), (5, 11), (2, 10), (1, 8), (4, 12), (7, 14)})

演示这里

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.