Создайте все возможные факторизации из списка основных факторов в 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. Краткий и простой в реализации на любом языке, который вы предпочитаете. Дело закрыто.


person Mr. T    schedule 06.11.2017    source источник
comment
Спасибо за форматирование моего первого поста, jmd_dk. Я принял к сведению изменения и постараюсь запомнить эти правила. Есть ли сдвиг вправо/влево для кода для правильного отступа или вам нужно вручную добавлять 4 пробела в каждую строку?   -  person Mr. T    schedule 07.11.2017
comment
Ошибка новичка — просто используйте кнопку {} для форматирования кода.   -  person Mr. T    schedule 08.12.2017


Ответы (1)


Ваша задача — определить мультипликативный раздел числа. Google должен указать вам, куда вам нужно идти. Stack Overflow уже имеет ответ.

person user448810    schedule 06.11.2017
comment
Очень признателен. Мультипликативный раздел. Неудивительно, я не нашел ответ без правильного ключевого слова. - person Mr. T; 07.11.2017