如何生成满足给定条件的所有可能组合以提高效率？

Question

（Python）我想要从一个包含150个数字的有序列表中生成长度为9的所有可能组合。但是，这并不是非常高效，因此我想要一个条件，即所选数字之间的差值不超过150，以便只生成我以后可以使用的组合。如何在Python中实现这一点？输入列表已经排序，我需要输出结果也是有序的。

我已经尝试了itertools的combinations函数，但正如我之前提到的那样，这并不高效，并且会产生超过10亿个可能的组合。

itertools.combinations(list, 9)

提前感谢！

我已经找到了这个很好的解决方案。然而，输出并没有排序，这就是我的问题。 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)]))

- JaKalli123

---

那么你列表中的内容可以是任何数字？有任何限制吗？你想从该列表中选择9个数字的组合，其中最小数字和最大数字之间不超过150个单位？你需要所有符合这个条件的组合，还是只需要一些即可？ - Simon Notley

排列没有顺序，而组合有，如果输入列表是有序的。itertools.combinations(iterable, r)： 它以排序的方式返回长度为 r 的元组，并且没有重复的元素。 - JaKalli123

你排序后的数据是否有重复元素？例如：[3, 4, 4, 5, 8, ...]。如果有，那么相同数字的组合应该被跳过吗？ - facehugger

@facehugger 不，列表中每个元素只出现一次。 - JaKalli123

@JaKali - 是的，抱歉我表达不清楚。我指的是在数学上，排列是按照它们的顺序和内容来定义的，而组合没有固有的顺序；只是它们出现在itertools中是有序的。如果你的意思是相邻元素在数字排序时之间的差异不超过150，那就很清楚了。这个限制可能会减少组合的数量，但并不清楚它是否会使找到组合的过程整体更快。 - Simon Notley

Answer 1

这就是它：

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

- facehugger

---

首先，非常感谢您的回答。然而，这并没有对我帮助太大，因为它仍然需要生成所有可能的组合，这并不是很高效的。这就是我的问题所在，我正在寻找一种只生成符合条件的组合的方法。 - JaKalli123

根据我的基准测试，这个解决方案非常高效；对于在0-5000范围内的150个随机数的样本输入，有大约1700万个组合符合条件，而这个解决方案在我的机器上运行时间不到16秒。而“生成所有并过滤”方法需要多年才能完成运行。@JaKalli123 - kaya3

Answer 2

这里提供了一个使用递归生成器函数的解决方案: 函数combinations_max_diff接受一个数字列表nums，一个元素数量k和一个最大差异值max_diff。

函数helper完成所有工作; 它接受一个部分组合comb，剩余元素数量r，下一个要选择的元素的最小列表索引i和控制下一个元素最大大小的max_next。

def combinations_max_diff(nums, k, max_diff):
    # input list must be sorted
    nums = sorted(nums)
    n = len(nums)

    def helper(comb, r, i, max_next):
        if r == 0:
            yield comb
        else:
            for ii in range(i, n - r + 1):
                v = nums[ii]
                if v > max_next: break
                comb_v = comb + (v,)
                yield from helper(comb_v, r - 1, ii + 1, v + max_diff)

    return helper((), k, 0, nums[-1])

使用示例：

>>> nums = [1, 2, 3, 4, 5, 6, 7]
>>> for c in combinations_max_diff(nums, 3, 2):
...     print(c)
... 
(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)
(3, 5, 7)
(4, 5, 6)
(4, 5, 7)
(4, 6, 7)
(5, 6, 7)

问题关注效率问题，以下是一些相关想法：

该问题涉及效率问题，因此以下提供一些相关想法：

>>> import random, timeit
>>> nums = sorted(random.randrange(0, 5000) for _ in range(150))
>>> len(list(combinations_max_diff(nums, 9, 150)))
16932905
>>> timeit.timeit(lambda: list(combinations_max_diff(nums, 9, 150)), number=1)
15.906288493999455

因此，在我的计算机上，生成大约17百万个组合需要约16秒钟，即每个组合不到一微秒。

- kaya3

---

据我理解，输入是一组排序好的数字集合。所以最好测试sorted(frozenset(random.randrange(0, 5000) for _ in range(150)))。 - facehugger

sorted 无论如何都会返回一个列表，过滤掉重复项只意味着大小不一定为150。即使有重复项，该算法也能完美地工作。 - kaya3

当然。我的结果太广泛了 - 从（我的18秒，你的26秒）到（我的3.2秒，你的4.1秒）。 - facehugger

@kaya3，你的解决方案运行时稳定吗？我知道我的解决方案在各种方面都不够优化，但是如果我得到一个连续块太大（即有太多连续数字而没有150的间隔），那么运行时间就会爆炸，因为itertools.combinations(block,9)需要很长时间。最坏的情况是整个东西都是一个大块，你又回到了150选9。 - Simon Notley

满足约束条件的所有组合的复杂度对于任何算法来说，都至少是符合条件的组合数量的线性级别。由于这些组合的数量在很大程度上取决于“nums”的分布，因此没有算法既高效又一致。更有用的度量方式是每个产生的组合的运行时间。 - kaya3