这就是它:
from itertools import combinations, islice, takewhile
def mad_combinations(data, comb_lenth, diff, create_comb=tuple):
assert comb_lenth >= 2
sorted_nums = sorted(frozenset(data))
stop_index = len(sorted_nums)
combination = [None]*comb_lenth
def last_combinator(start_index, right_max_number):
"""Last combination place loop"""
return takewhile(right_max_number.__ge__, islice(sorted_nums, start_index, stop_index))
def _create_combinator(next_place_combinator, current_combination_place):
def combinator(start_index, right_max_number):
"""Main loop"""
for i, combination[current_combination_place] in \
enumerate(
takewhile(
right_max_number.__ge__,
islice(sorted_nums, start_index, stop_index)),
start_index + 1):
yield from (
next_place_combinator(i, combination[current_combination_place] + diff))
return combinator
for combination_place in range(comb_lenth-2, 0, -1):
last_combinator = _create_combinator(last_combinator, combination_place)
last_index = comb_lenth - 1
for j, combination[0] in enumerate(sorted_nums, 1):
for combination[last_index] in last_combinator(j, combination[0] + diff):
yield create_comb(combination)
上面的函数大致相当于:
def example_of_comb_length_3(data, diff):
sorted_nums = sorted(frozenset(data))
for i1, n1 in enumerate(sorted_nums, 1):
for i2, n2 in enumerate(sorted_nums[i1:], i1 + 1):
if n2 - n1 > diff:break
for n3 in sorted_nums[i2:]:
if n3 - n2 > diff:break
yield (n1, n2, n3)
使用筛选器的版本:
def insane_combinations(data, comb_lenth, diff):
assert comb_lenth >= 2
for comb in combinations(sorted(frozenset(data)), comb_lenth):
for left, right in zip(comb, islice(comb, 1, comb_lenth)):
if right - left > diff:
break
else:
yield comb
def crazy_combinations(data, comb_lenth, diff):
assert comb_lenth >= 2
last_index = comb_lenth - 1
last_index_m1 = last_index - 1
last_rule = (lambda comb: comb[last_index] - comb[last_index_m1] <= diff)
_create_rule = (lambda next_rule, left, right:
(lambda comb: (comb[right] - comb[left] <= diff) and next_rule(comb)))
for combination_place in range(last_index_m1, 0, -1):
last_rule = _create_rule(last_rule, combination_place - 1, combination_place)
return filter(last_rule, combinations(sorted(frozenset(data)), comb_lenth))
测试:
def test(fetch, expected, comb_length, diff):
fetch = tuple(fetch)
assert list(insane_combinations(fetch, comb_length, diff)) == \
list(crazy_combinations(fetch, comb_length, diff)) == \
list(mad_combinations(fetch, comb_length, diff)) == list(expected)
if __name__ == '__main__':
test([1,2,3,4,5,6],
comb_length=3, diff=2,
expected=[
(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 3, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5),
(2, 4, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)])
test([1, 2, 3, 8, 9, 10, 11, 12, 13],
comb_length=3, diff=3,
expected=[
(1, 2, 3), (8, 9, 10), (8, 9, 11), (8, 9, 12), (8, 10, 11), (8, 10, 12),
(8, 10, 13), (8, 11, 12), (8, 11, 13), (9, 10, 11), (9, 10, 12), (9, 10, 13),
(9, 11, 12), (9, 11, 13), (9, 12, 13), (10, 11, 12), (10, 11, 13), (10, 12, 13),
(11, 12, 13)])
我没有过多考虑边缘案例!!我仅测试了这两个获取操作! 如果您发现我的回答有帮助,请务必测试所有可能选项,并写出发现的错误(我认为会有很多错误)。要检查您的具体获取操作,请使用mad_combinations(your_fetch, 9, 150)
。