не простые множители с некоторыми повторениями

Question

Допустим, у нас есть числовые коэффициенты, например 1260:

>>> factors(1260)
[2, 2, 3, 3, 5, 7]

Что было бы наилучшим способом сделать в комбинациях Python с каждым возможным субпродуктом из этих чисел, то есть со всеми факторингами, а не только с простым факторингом, с суммой факторов меньше max_product ?

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

Я также могу уточнить свою функцию делителей , чтобы производить пары делителей вместо делителей в порядке размера, но все же это будет стоить мне сделать это для числа с product до 12000 . Продукт должен всегда оставаться неизменным.

Я был связан с делителем, но это не стоило усилий, чтобы доказать, что они приняли мой другой код. По крайней мере, моя функция делителя заметно быстрее, чем симпти:

def divides(number):
    if number<2:
        yield number
        return
    high = [number]
    sqr = int(number ** 0.5)
    limit = sqr+(sqr*sqr != number)
    yield 1
    for divisor in xrange(3, limit, 2) if (number & 1) else xrange(2, limit):
        if not number % divisor:
            yield divisor
            high.append(number//divisor)
    if sqr*sqr== number: yield sqr
    for divisor in reversed(high):
        yield divisor

Единственная проблема для повторного использования этого кода - это связать делители с разложением по разрядам или сделать что-то вроде itertools.product делителей делителей в парах, которые я бы выдал в виде пар вместо сортировки по порядку.

Примером результатов будет:

[4, 3, 3, 5, 7] (one replacement of two)
[5, 7, 36] (one replacement of three)
[3, 6, 14, 5] (two replacements)

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

ОБНОВЛЕНИЕ: сумма факторов должна быть близка к продукту, поэтому, вероятно, в ответе большое количество факторов <= 10 (до 14 факторов). </strong>

UPDATE2: Вот мой код, но я должен выяснить, как сделать многократное удаление рекурсивно или итеративно для частей длиной> 2 и выкопать лексическое разбиение, чтобы заменить шаблоны скачкообразных битов, которые производят дубликаты (количество жалких обращений только для одной замены, а это не посчитать прохождение «разбиений одного элемента» внутри single_partition):

from __future__ import print_function
import itertools
import operator
from euler import factors

def subset(seq, mask):
    """ binary mask of len(seq) bits, return generator for the sequence """
    # this is not lexical order, replace with lexical order masked passing duplicates
    return (c for ind,c in enumerate(seq) if mask & (1<<ind))


def single_partition(seq, n = 0, func = lambda x: x):
    ''' map given function to one partition  '''
    for n in range(n, (2**len(seq))):
        result = tuple(subset(seq,n))
        others = tuple(subset(seq,~n))
        if len(result) < 2 or len(others) == 0:
            #empty subset or only one or all
            continue
        result = (func(result),)+others
        yield result


if __name__=='__main__':
    seen,  hits, count = set(), 0, 0
    for f in single_partition(factors(13824), func = lambda x: reduce(operator.mul, x)):
        if f not in seen:
            print(f,end=' ')
            seen.add(f)
        else:
            hits += 1
        count += 1
    print('\nGenerated %i, hits %i' %(count,hits))

Уточнение Я рад получить только факторинги с макс. 5 факторами в непростых факторных частях. Я обнаружил от руки, что по этой форме следуют неубывающие договоренности по 5 одинаковым факторам:

partitions of 5    applied to 2**5
1  1  1   1  1     2  2   2   2  2
1  1  1     2      2  2   2    4
1  1  1  3         2  2      8
1   2       2      2    4      4 
1       4          2      16
  2      3           4       8

РЕШЕНИЕ Я не убираю принятый ответ из хорошего решения, но он слишком сложен для работы. Из Project Euler я раскрываю только эту вспомогательную функцию из orbifold of NZ, она работает быстрее и не нуждается в простых факторах:

def factorings(n,k=2):
    result = []
    while k*k <= n:
        if n%k == 0:
            result.extend([[k]+f for f in factorings(n/k,k)])
        k += 1
    return result + [[n]]

Соответствующее решение для проблемы 88 его запуска в Python 2.7 за 4,85 с моим декоратором синхронизации и после оптимизации условия остановки с помощью найденного счетчика 3,4 с в 2.6.6 с psyco , 3,7 с в 2,7 без психо. Скорость моего собственного кода возросла с 30 секунд с кодом в принятом ответе (добавленная мной сортировка удалена) до 2,25 с (2,7 без психо) и 782 мс с психо в Python 2.6.6.

Answer 1

from __future__ import print_function
import itertools
import operator

def partition(iterable, chain=itertools.chain, map=map):
    # http://code.activestate.com/recipes/576795/
    # In [1]: list(partition('abcd'))
    # Out[1]: 
    # [['abcd'],
    #  ['a', 'bcd'],
    #  ['ab', 'cd'],
    #  ['abc', 'd'],
    #  ['a', 'b', 'cd'],
    #  ['a', 'bc', 'd'],
    #  ['ab', 'c', 'd'],
    #  ['a', 'b', 'c', 'd']]    
    s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable)
    n = len(s)
    first, middle, last = [0], range(1, n), [n]
    getslice = s.__getslice__
    return [map(getslice, chain(first, div), chain(div, last))
            for i in range(n) for div in itertools.combinations(middle, i)]

def product(factors,mul=operator.mul):
    return reduce(mul,factors,1)

def factorings(factors,product=product,
               permutations=itertools.permutations,
               imap=itertools.imap,
               chain_from_iterable=itertools.chain.from_iterable,
               ):
    seen=set()
    seen.add(tuple([product(factors)]))
    for grouping in chain_from_iterable(
        imap(
            partition,
            set(permutations(factors,len(factors)))
            )):
        result=tuple(sorted(product(group) for group in grouping))
        if result in seen:
            continue
        else:
            seen.add(result)
            yield result

if __name__=='__main__':
    for f in factorings([2,2,3,3,5,7]):
        print(f,end=' ')

урожайность

(3, 420) (9, 140) (28, 45) (14, 90) (2, 630) (3, 3, 140) (3, 15, 28) (3, 14, 30) (2, 3, 210) (5, 9, 28) (9, 10, 14) (2, 9, 70) (2, 14, 45) (2, 7, 90) (3, 3, 5, 28) (3, 3, 10, 14) (2, 3, 3, 70) (2, 3, 14, 15) (2, 3, 7, 30) (2, 5, 9, 14) (2, 7, 9, 10) (2, 2, 7, 45) (2, 3, 3, 5, 14) (2, 3, 3, 7, 10) (2, 2, 3, 7, 15) (2, 2, 5, 7, 9) (2, 2, 3, 3, 5, 7) (5, 252) (10, 126) (18, 70) (6, 210) (2, 5, 126) (5, 14, 18) (5, 6, 42) (7, 10, 18) (6, 10, 21) (2, 10, 63) (3, 6, 70) (2, 5, 7, 18) (2, 5, 6, 21) (2, 2, 5, 63) (3, 5, 6, 14) (2, 3, 5, 42) (3, 6, 7, 10) (2, 3, 10, 21) (2, 3, 5, 6, 7) (2, 2, 3, 5, 21) (4, 315) (20, 63) (2, 2, 315) (4, 5, 63) (4, 9, 35) (3, 4, 105) (7, 9, 20) (3, 20, 21) (2, 2, 9, 35) (2, 2, 3, 105) (4, 5, 7, 9) (3, 4, 5, 21) (3, 3, 4, 35) (3, 3, 7, 20) (2, 2, 3, 3, 35) (3, 3, 4, 5, 7) (7, 180) (3, 7, 60) (2, 18, 35) (2, 6, 105) (3, 10, 42) (2, 3, 6, 35) (15, 84) (12, 105) (3, 5, 84) (5, 12, 21) (7, 12, 15) (4, 15, 21) (2, 15, 42) (3, 5, 7, 12) (3, 4, 7, 15) (2, 6, 7, 15) (2, 2, 15, 21) (21, 60) (30, 42) (6, 7, 30) (5, 7, 36) (2, 21, 30) (5, 6, 6, 7) (3, 12, 35) (6, 14, 15) (4, 7, 45) (35, 36) (6, 6, 35)

Answer 2

Я использую список типа [(2, 9), (3, 3)] (для [2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]) в качестве базового списка нерасширенных факторов и списка расширенных факторов.В каждом раунде я выбираю один фактор из базы, уменьшая его количество, и

• добавляю его в расширенный список, увеличивая его длину, поэтому у нас есть всего один дополнительный фактор (до cufoff)
• умножьте его на все расширенные факторы, генерируя все возможности

Благодаря динамическому программированию и стратегии отсечения это стало чрезвычайно быстрым:

from itertools import groupby

def multiplicies( factors ):
    """ [x,x,x,,y,y] -> [(x,3), (y,2)] """
    return ((k, sum(1 for _ in group)) for k, group in groupby(factors))

def combinate(facs, cutoff=None):
    facs = tuple(multiplicies(facs))

    results = set()
    def explode(base, expanded):
        # `k` is the key for the caching
        # if the function got called like this before return instantly
        k = (base, expanded)
        if k in results:
            return
        results.add(k)

        # pick a factor
        for (f,m) in base:
            # remove it from the bases
            newb = ((g, (n if g!=f else n-1)) for g,n in base)
            newb = tuple((g,x) for g,x in newb if x > 0)

            # do we cutoff yet?
            if cutoff is None or len(newb) + len(expanded) < cutoff:
                explode(newb, tuple(sorted(expanded + (f,))))

            # multiply the pick with each factor in expanded
            for pos in range(len(expanded)):
                newexp = list(expanded)
                newexp[pos] *= f
                explode(newb, tuple(sorted(newexp)))

    explode(facs, ())
    # turn the `k` (see above) into real factor lists
    return set((tuple((x**y) for x,y in bases) + expanded) 
        for (bases, expanded) in results)

# you dont even need the cutoff here!
combinate([2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3])
# but you need it for 
combinate([2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3,5,7,9,11], 5)

Попробуйте Psyco если вы можете (я не могу, потому что у меня только Py2.7 здесь), это может также немного ускорить это.

Answer 3

То, что вы ищете, чаще всего называется делителем . Ответы на этот вопрос могут вам помочь.