一些重複

Question

非黃金factorings比方說，我們有一個數字的因素，例如1260：

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

這將是Python的組合與每個子產品可能從這些數字，即所有factorings做的最好的辦法，不僅質量保證，因子總和小於max_product？

如果我從素數因素進行組合，我不得不重構產品的剩餘部分，因爲我不知道其餘部分沒有組合。

我還可以改進我的除數功能來生成對除數，而不是在大小順序的除數，但它仍然會花費我產品做到這一點的數量高達12000。產品必須始終保持不變。

我被連接到除數例程，但它看起來並不值得努力證明它們採用我的其他代碼。至少我的除數功能noticably快於sympy之一：

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個因子）。

UPDATE2： 這裏是我的代碼，但必須弄清楚如何遞歸或迭代零件> 2長期做多的清除和挖掘詞彙分區，以取代會產生重複，跳躍位模式（可憐的命中只算一個替代，而且不計single_partition內「單元素partionings」）的傳：

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個因素factorings在非主要因素部分。我已經用手發現非遞減長達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 

的解決方案 我沒有從細解下來接受的答案，但它是在複雜的工作。從項目歐拉我只揭示了來自新西蘭的orbifold這個輔助功能，它的工作速度更快，而無需先的主要因素：由

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小號我的計時裝飾器，並在找到計數器優化停止條件後2.6.6與psyco 3.4秒，2.7秒3.7秒沒有psyco。速度我自己的代碼從代碼中接受的答案（我刪除排序添加到）2.25秒（2.7無psyco）和782毫秒與Python 2.6.6中的psyco。

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

你在找什麼更通常被稱爲除數。 this question的答案可能對您有所幫助。

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)