时间戳

首页 > 解决方案 > 从给定的一组数字中找出适用于某些规则的所有组合

python - 从给定的一组数字中找出适用于某些规则的所有组合

问题描述

感谢您对以下问题的帮助：

我有一个数字列表和一本字典：

my_list = [400, 200, 100, 50, 25]
my_dict = {400: 8, 200:4, 100: 2, 50: 2, 25: 2}

当他们应该应用以下规则时，我需要找到可能从 my_list 中的数字构建的所有可能组合：

  1. 相同的数字可能在组合中（[400, 400, 400]是有效的组合）
  2. 顺序无关紧要（和我[400, 200, 100]一样[100, 200, 400]）
  3. 组合中的数字之和不应超过1200
  4. 的总和my_dict[my_list_item]不应超过 24（例如无效，[400, 400, 400, 100]因为my_dict[400]+my_dict[400]+my_dict[400]+my_dict[100] = 8+8+8+2 = 26，因此它不是有效的组合）

python算法解决这个问题的任何想法。谢谢

标签： pythonalgorithmstatistics

解决方案

这是使用迭代器递归执行此操作的代码，以避免在内存中持有过多。

#! /usr/bin/env python3

def combs (numbers, value_of, max_numbers=1200, max_value=24, min_i=0):
    if len(numbers) <= min_i:
        yield []
    else:
        for comb in combs(numbers, value_of, max_numbers, max_value, min_i+1):
            yield comb
            comb_copy = [n for n in comb] # Copy to avoid sharing bugs.
            numbers_sum = sum(comb)
            values_sum = sum([value_of[i] for i in comb])
            while True:
                comb_copy.append(numbers[min_i])
                numbers_sum += numbers[min_i]
                if max_numbers < numbers_sum:
                    break
                values_sum += value_of[numbers[min_i]]
                if max_value < values_sum:
                    break
                yield comb_copy


my_list = [400, 200, 100, 50, 25]
my_dict = {400: 8, 200:4, 100: 2, 50: 2, 25: 2}

for c in combs(my_list, my_dict):
    print(c)

推荐阅读