(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)
提前致谢#
我已经找到了这个解决方案，非常好.但是输出没有排序，这是我的问题.导入迭代工具随机导入
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)]))
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)
使用过滤器的版本:
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)])
我并没有太在意边缘情况！而且我只测试了这 2 次提取！ 如果您发现我的回答有帮助，请务必测试所有可能的选项并写下发现的错误(我认为很多错误).要检查您的具体获取，请使用 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).
这篇关于如何在给定条件下生成所有可能的组合以提高效率?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！