如何在给定条件下生成所有可能的组合以使其更有效率？

Question

（Python）我想从150个数字的排序列表中生成长度为9的所有可能组合。但是，这不是很有效，因此我想让每个选定数字之间的差值等于或小于150，以便仅生成组合，以便以后使用。如何在Python中实现？输入列表已排序，我也需要对输出进行排序。

我已经从itertools中尝试了组合功能，但是正如我已经提到的那样，这种方法效率不高，可能会产生十亿种以上的组合。

itertools.combinations(list, 9)

提前致谢＃

我已经找到了这个解决方案，非常好。但是输出没有排序，这是我的问题。导入itertools随机导入

def combs(nums):
    result = set()
    for lower in nums:
        options = [n for n in nums if lower <= n <= lower + 150]
        result.update(itertools.combinations(options, 9))
    return result

print(combs([random.randrange(0, 5000) for _ in range(150)]))

Answer 1

Here it is:

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) # or use None - what is faster?
    combination = [None]*comb_lenth # common memory

    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))
        # In other words:
        # for x in islice(sorted_nums, start_index, stop_index):
        #     if x <= right_max_number:
        #         yield x
        #     else: return

    def _create_combinator(next_place_combinator, current_combination_place):
        # this namespace should store variables above
        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 ( # it yields last combination place number
                    next_place_combinator(i, combination[current_combination_place] + diff))

        return combinator

    for combination_place in range(comb_lenth-2, 0, -1): # create chain of loops
        last_combinator = _create_combinator(last_combinator, combination_place)

    last_index = comb_lenth - 1
    # First combination place loop:
    for j, combination[0] in enumerate(sorted_nums, 1):
        for combination[last_index] in last_combinator(j, combination[0] + diff):
            yield create_comb(combination) # don't miss to create a copy!!!

The function above is roughly equivalent to:

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)

Versions that use filter:

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))

Tests:

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)])

我不太关心边缘情况！我只测试了这 2 个获取！如果您发现我的答案有帮助，请务必测试所有可能的选项并写下发现的错误（我认为有很多错误）。要检查您的具体获取使用mad_combinations(your_fetch, 9, 150)。