Python 3-通过循环重建给定集合来减少列表 [英] Python 3 - Reducing a list by cyclical reconstructing a given set

问题描述

我正在寻找一种算法，该算法通过将给定的集合重构为模式来减少循环的元组列表。

I am looking for an algorithm that reduces a list of tuples cyclical by reconstructing a given set as pattern.

每个元组都包含一个id和一个集合，例如（1，{'xy'}）。

Each tuple contains an id and a set, like (1, {'xy'}).

示例

query = {'xyz'}

my_dict = [(1, {'x'}), (2, {'yx'}), (3, {'yz'}),
           (4, {'z'}), (5, {'x'}), (6, {'y'}), 
           (7, {'xyz'}), (8, {'xy'}), (9, {'x'}),]

目标是根据 xyz 尽可能多地重新创建模式 xyz c $ c> my_dict 。

The goal is to recreate the pattern xyz as often as possible given the second value of the tuples in my_dict. Remaining elements from which the query set can not be completely reconstructed shall be cut off, hence 'reduce'.

my_dict

my_dict contains in total: 6 times x, 5 times y, 3 times z.

考虑 my_dict ，有效的解决方案例如是：

Considering the my_dict, valid solutions would be for example:

result_1 = [(7, {'xyz'}), (8, {'xy'}), (4, {'z'}), (1, {'x'}), (3, {'yz'})]
result_2 = [(7, {'xyz'}), (2, {'yx'}), (4, {'z'}), (1, {'x'}), (3, {'yz'})]
result_3 = [(7, {'xyz'}), (9, {'x'}), (6, {'y'}), (4, {'z'}), (1, {'x'}), (3, {'yz'})]

列表中元组的顺序并不重要，我按查询模式<$ c的顺序对它们进行了排序$ c> xyz 出于说明目的。

The order of the tuples in the list is NOT important, i sorted them in the order of the query pattern xyz for the purpose of illustration.

目标

目标是要有一个元组列表，其中查询集中元素出现的总数是最佳的最佳均匀分布

The goal is to have a list of tuples where the total number of occurrences of the elements from the query set is most optimal evenly distributed.

result_1 ， result_2 和 result_3 总共包含： x 的3倍， y 的3倍， z 的3倍。

result_1, result_2 and result_3 all contain in total: 3 times x, 3 times y, 3 times z.

有人知道怎么做吗？

感谢您的帮助！

推荐答案

取决于您的应用程序上下文，它是幼稚的蛮力方法可能就足够了：使用此SO答案中的 powerset 函数，

Depending on your application context, a naive brute-force approach might be enough: using the powerset function from this SO answer,

def find_solutions(query, supply):
    for subset in powerset(supply):   
        if is_solution(query, subset):
            yield subset

您需要实现一个函数 is_solution（query，subset），当给定的供应子集时返回 True （ my_dict。 values（））是给定查询的有效解决方案。

You would need to implement a function is_solution(query, subset) that returns True when the given subset of the supply (my_dict.values()) is a valid solution for the given query.

这篇关于Python 3-通过循环重建给定集合来减少列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！