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

Question

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

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

Что было бы наилучшим способом сделать в комбинациях Python с каждым возможным субпродуктом из этих чисел, то есть со всеми факторингами, а не только с простыми факторингами, с суммой факторов меньше, чем max_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 факторов).

ОБНОВЛЕНИЕ 2: Вот мой код, но я должен выяснить, как сделать многократное удаление рекурсивно или итеративно для частей длиной> 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 с психо, 3,7 с в 2,7 без психо. Скорость моего собственного кода увеличилась с 30 секунд с кодом в принятом ответе (сортировка добавлена ​​мной удалена) до 2,25 с (2,7 без психо) и 782 мс с психо в Python 2.6.6.

Answer 1

Я использую список как [(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 2

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

Answer 3

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)