python - 消除连续数字

Question

如果您有 1-49 范围内的数字，有 6 个数字可供选择，则有将近 1400 万种组合。使用我当前的脚本，我目前只剩下 720 万个组合。在剩下的 720 万个组合中，我想消除所有 3、4、5、6、双和三连号。示例:

• 连续 3 个:1、2、3、x、x、x
• 连续 4 个:3、4、5、6、x、x
• 连续 5 次:4、5、6、7、8、x
• 连续 6 个:5、6、7、8、9、10
• 双分离连续:1、2、5、6、14、18
• 三次独立连续:1、2、9、10、22、23

注意:1、2、12、13、14、15等组合也必须被淘汰，否则与双连、三连连组合被淘汰的规则相冲突。

我正在寻找剩余的 720 万个组合中有多少个组合具有零个连续数字(全部混合)并且只有 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))

Answer 1

虽然我的回答应该有效，但我认为有人可以提供更快的解决方案。

考虑以下代码:

not_allowed = []
for x in range(48):
    not_allowed.append([x, x+1, x+2])

# not_allowed = [ [0,1,2], [1,2,3], ... [11,12,13], ... [47,48,49] ]
my_numbers = [[1, 2, 5, 9, 11, 33], [1, 3, 7, 8, 9, 31], [12, 13, 14, 15, 23, 43]]
for x in my_numbers:
    for y in not_allowed:
        if set(y) <= set(x): # if [1,2,3] is a subset of [1,2,5,9,11,33], etc.
            # drop x

此代码将删除所有包含双连续数字的实例，这是您真正需要检查的所有实例，因为三重、四重等都意味着双连续。尝试实现它并让我知道它是如何工作的。