Есть ли более быстрый / оптимизируемый способ найти уникальные комбинации из набора / списка уникальных элементов в Python

Я пытаюсь найти все возможные уникальные комбинации из n элементов, взятых по m за раз. Я использовал itertools.combinations для того же, и у меня есть n = 85. Поэтому, когда я нахожу комбинации для m = 5, количество созданных комбинаций составляет около 3 cr, и это занимает много времени, поскольку на данный момент элементы представляют собой список строк, или, точнее, это столбцы в алфавитном порядке, не числовые индексы. В настоящее время я работаю с pandas и itertools.combinations, хотел бы знать, можно ли распараллелить процесс поиска комбинаций, чтобы каждый раз давать одинаковые результаты при дальнейших вычислениях, которые я выполнить дальнейшую работу со столбцами, или может ли фреймы данных графического процессора, такие как cuDF, оптимизировать это, хотя это не похоже на это. Кроме того, может ли преобразование имен столбцов в числа, а затем преобразование их в массив чисел работать быстрее при поиске комбинаций? Пожалуйста, также предложите решения, где это можно было бы сделать быстрее и на другом языке программирования. Не очень хороший программист. Хотелось бы увидеть математические и программные решения с помощью анализа сложности.


person Sakshi Tantak    schedule 10.04.2020    source источник


Ответы (1)


Это как раз проблема анализа сложности, и нет никакого способа распараллелить ее таким образом, чтобы это было удовлетворительно. С n=85 и m=5 возможны 85^5 = 4437053125 комбинации, включая развороты и дубликаты.

Самый быстрый из известных мне способов использования графического процессора для исследования этого пространства - это cuGraph. Изучение всех комбинаций 4437053125 - это просто поиск в ширину, хотя даже с графическим процессором я ожидаю, что это займет очень много времени.

Искусственный интеллект - это изучение методов поиска полезных решений внутри проблемных пространств, которые слишком велики, чтобы их можно было полностью исследовать. * Или жадный поиск может быстро дать вам хорошее решение, если есть какая-то метрика, которую вы пытаетесь оптимизировать среди 85^5 общих комбинаций.

person Thomson Comer    schedule 15.04.2020