组合组合

Question

在1-49的范围内，从6个数字中选出了近1400万个组合。从1400万，我已经削减到890万的组合，只选择那些6的数字组合之和必须等于120到180之间。

例: 5，10，20，27，29，40 = 131

在剩下的890万个组合中，我试图删除所有包含小于2个和4个以上奇数的组合。

基本上，我想让Python向我展示这890万个组合中有多少个组合中有2-4个奇数。所有只有1个或更少奇数和5个或更多奇数的组合将被排除在结果之外。

例子: 5，10，20，27，32，40 =2个奇数(它将包含在组合的数量中)。

谢谢!

import functools

_MIN_SUM     = 120
_MAX_SUM     = 180
_MIN_NUM     = 1
_MAX_NUM     = 49
_NUM_CHOICES = 6

@functools.lru_cache(maxsize=None)
def f(n, l, s):
    assert(all(isinstance(v, int) and v >= 0 for v in (n, l, s)))
    return 0 if s > _MAX_SUM else (
        int(s >= _MIN_SUM) if n == 0 else (
            sum(f(n-1, i+1, s+i) for i in range(l, _MAX_NUM+1))
        )
    )

result = f(_NUM_CHOICES, _MIN_NUM, 0)

print('Number of choices = {}'.format(result))

Answer 1

你可以和你现在做的几乎完全一样。只需添加一个参数来计算有多少个奇数，并在添加一个奇数时增加它。然后，您可以相应地调整测试：

import functools

_MIN_SUM     = 120
_MAX_SUM     = 180
_MIN_NUM     = 1
_MAX_NUM     = 49
_NUM_CHOICES = 6
_MIN_ODDS    = 2
_MAX_ODDS    = 4

@functools.lru_cache(maxsize=None)
def f(n, l, s = 0, odds = 0):
    if s > _MAX_SUM or odds > _MAX_ODDS:
        return 0
    if n == 0 :
        return int(s >= _MIN_SUM and odds >= _MIN_ODDS)
    return sum(f(n-1, i+1, s+i, odds + i % 2) for i in range(l, _MAX_NUM+1))


result = f(_NUM_CHOICES, _MIN_NUM)

print('Number of choices = {}'.format(result))

因为它是回忆录和修剪树枝，所以它运行得很快：

150 ns ± 13 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

以更可管理的方式运行它：

_MIN_SUM     = 1
_MAX_SUM     = 8
_MIN_NUM     = 1
_MAX_NUM     = 8
_NUM_CHOICES = 2
_MIN_ODDS    = 2
_MAX_ODDS    = 4

返回4，它对应于集合：

(1, 3),
(1, 5),
(1, 7),
(3, 5)

Answer 2

您可以使用itertools中的组合()函数，只需对符合条件的组合进行残酷的计数：

from itertools import combinations

eligible = 0
for combo in combinations(range(1,50),6):
    total = sum(combo)
    if total < 120 or total > 180:
        continue
    odds = sum(n&1 for n in combo)
    if odds < 2 or odds > 4:
        continue
    eligible += 1

print(eligible) # 7221936

它只需要几秒钟(10-12)