Создайте все возможные факторизации из списка простых факторов в Python

Mr. T спросил: 13 октября 2017 в 06:58 в: python

Хотя я видел сообщения о поиске простых факторов и делителей, я не нашел ответа на свой вопрос о факторизации в Python. У меня есть список основных факторов, то есть для 24 это [2,2,2,3]. Я хочу из этого списка все возможные факторизации, то есть для 24 выходные данные должны быть [[2,12], [3,8], [4,6], [2,2,6], [2,3,4], [2,2,2,3]]. Я пробовал подходы itertool, но это создавало множество дублирующих ответов и забывало другие (например, поиск [2,3,4], но игнорируя [4,6]).

Меня особенно интересует подход, использующий сгенерированный список простых факторов. Я нашел обходной путь с рекурсивной функцией.

def factors(n, n_list):                 
    for i in range(2, 1 + int(n ** .5)):
        if n % i == 0:
            n_list.append([i, n // i])
            if n // i not in primes:  #primes is a list containing prime numbers
                for items in factors(n // i, []):
                    n_list.append(sorted([i] + items))
    fac_list = [[n]]                  #[n] has to be added manually
    for facs in n_list:               #removes double entries     
        if facs not in fac_list:
            fac_list.append(facs)
    return fac_list

Но это занимает много времени для больших n, так как он должен просматривать все числа, а не только простые числа. Комбинаторный подход к списку простых факторов должен быть намного быстрее.

Редактировать. После просмотра нескольких ресурсов лучшее объяснение хорошей стратегии - это ответ с наивысшим рейтингом здесь, на SO . Краткий и простой в реализации на любом языке, предпочитаете. Дело закрыто.

0 ответов