我试图从 n 个元素中找到所有可能的唯一组合，一次取 m 个。我已经使用了itertools.combinations并且我有n=85。因此，当我找到m=5的组合时，产生的组合数量约为 3 cr，这需要很长时间，因为到目前为止，元素是字符串列表，或者更准确地说，它们是按字母顺序排列的列，而不是数字索引。我目前正在使用pandas和 itertools.combinations，想知道查找组合的过程是否可以并行化，每次在我进一步对列执行的进一步计算时给出相同的结果，或者GPU 数据帧（如 cuDF）是否可以优化这一点，尽管它看起来不像。此外，是否可以将列名转换为数字，然后将其转换为numpy 数组以在查找组合的同时更快地工作？还请提出解决方案，在这些解决方案中，这也可以在其他一些编程语言中更快地完成。不是一个很好的程序员。希望看到一些具有复杂性分析的数学和编程解决方案。
问问题
126 次
1 回答
1
This is exactly a complexity analysis problem, and there's no way to parallelize it in a way that will be satisfying. With n=85 and m=5, there are 85^5 = 4437053125 possible combinations, including reversals and duplicates.
The fastest way that I know of using a GPU to explore this space is with cuGraph. Exploring all 4437053125 combinations is simply a breadth first search, though even with a GPU I expect it to take a very long time.
Artificial Intelligence is the study of methods of finding useful solutions inside of problem spaces that are too big to fully explore. A* or greedy search could give you a good solution, quickly, assuming that there is some metric that you are trying to optimize among the 85^5 total combinations.
于 2020-04-15T18:58:19.723 回答