如何在给定条件下生成所有可能的组合以使其更有效率？ [英] How to generate all possible combinations with a given condition to make it more efficient?

问题描述

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

(Python) I would like to generate all possible combinations with length 9 out of a sorted list list with 150 numbers. However, that's not very efficient, so I want to have a condition where the difference between each of the selected numbers is 150 or less in order to only generate combinations, that I can use later on. How can I achieve this in Python? The input list is sorted and I need the output to be sorted as well.

我已经尝试过itertools的组合功能，但是正如我已经提到的那样，这并不高效且会产生超过十亿种可能的组合。

I already tried the combinations function from itertools, but as I already mentioned, that's not efficient and would produce more than a billion possible combinations.

itertools.combinations(list, 9)

预先感谢＃

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

I already found this solution, which was very good. However the output wasn't sorted which was my problem. import itertools import random

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

推荐答案

在这里是：

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

以上功能大致等同于：

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）。

I did not bother much with edge cases!! And I've tested only these 2 fetches! If you will find my answer helpful, be sure to test all possible options and write about bugs found (many bugs, I think). To check your concrete fetch use mad_combinations(your_fetch, 9, 150).

这篇关于如何在给定条件下生成所有可能的组合以使其更有效率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！