具有一些重复的非素数因式分解
假设我们有数字因子，例如 1260：
>>> factors(1260)
[2, 2, 3, 3, 5, 7]
这将是在 Python 中组合这些数字可能的每个子乘积的最佳方法，即所有因式分解，而不仅仅是素数因式分解，因数之和更少比max_product？
如果我从主要因素进行组合，我必须重构产品的剩余部分，因为我不知道未组合的剩余部分。
我还可以改进我的除数函数来生成除数对，而不是按大小顺序生成除数，但是对于乘积高达 12000 的数字执行此操作仍然会花费我的成本。产品必须始终保持不变。
我与除数例程相关联，但看起来不值得努力证明它们适用于我的其他代码。至少我的除数函数明显比 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 个因子）。
更新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))
REFINMENT 我很高兴只得到非质因数部分中最多 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 中，我只展示了来自 NZ 的 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]]
根据我的计时，他在 Python 2.7 中运行的问题 88 的相关解决方案在 4.85 秒内装饰器并在优化停止条件后发现计数器 3.4 s in 2.6.6 with psyco, 3.7 s in 2.7 without psyco 。 我自己的代码的速度从接受答案中的代码的 30 秒（删除了我添加的排序）到 2.25 秒（没有 psyco 时为 2.7），在 Python 2.6.6 中使用 psyco 时为 782 毫秒。
Let's say we have numbers factors, for example 1260:
>>> factors(1260)
[2, 2, 3, 3, 5, 7]
Which would be best way to do in Python combinations with every subproduct possible from these numbers, ie all factorings, not only prime factoring, with sum of factors less than max_product?
If I do combinations from the prime factors, I have to refactor remaining part of the product as I do not know the remaining part not in combination.
I can also refine my divisors function to produce pairs of divisors instead of divisors in size order, but still it will cost me to do this for number with product upto 12000. The product must remain always the same.
I was linked to divisor routine, but it did not look worth the effort to prove them to adopt to my other code. At least my divisor function is noticably faster than sympy one:
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
Only problem to reuse this code is to link the divisors to factoring sieve or do some kind of itertools.product of divisors of the divisors in pairs, which I would give out as pairs instead of sorting to order.
Example results would be:
[4, 3, 3, 5, 7] (one replacement of two)
[5, 7, 36] (one replacement of three)
[3, 6, 14, 5] (two replacements)
Probably I would need some way to produce sieve or dynamic programming solutions for smaller divisors which could be linked to numbers whose divisors they are. Looks difficult to avoid overlap though. I do have one sieve function ready which stores biggest prime factor for each number for speeding up the factoring without saving complete factorings of every number... maybe it could be adapted.
UPDATE: The sum of factors should be near the product, so probably there is high number of factors of <= 10 in answer (upto 14 factors).
UPDATE2:
Here is my code, but must figure out how to do multiple removals recursively or iteratively for parts > 2 long and dig up the lexical partitioning to replace the jumping bit patterns which produce duplicates (pathetic hit count only for one replacement, and that does not count the passing of 'single element partionings' inside the 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))
REFINEMENT I am happy to get only the factorings with max 5 factors in the non-prime factor parts. I have found by hand that non-decreasing arrangements for up to 5 same factors follow this form:
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
THE SOLUTION
I do not remove the accepted answer from fine solution down, but it is over complicated for the job. From Project Euler I reveal only this helper function from orbifold of NZ, it works faster and without needing the prime factors first:
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]]
The relevant solution for problem 88 of his run in Python 2.7 in 4.85 s by my timing decorator and after optimizing the stop condition by found counter 3.4 s in 2.6.6 with psyco, 3.7 s in 2.7 without psyco . Speed of my own code went from 30 seconds with code in accepted answer (sorting added by me removed) to 2.25 s (2.7 without psyco) and 782 ms with psyco in Python 2.6.6.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
发布评论
评论（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)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
我使用像
[(2, 9), (3, 3)]这样的列表（对于[2, 2, 2, 2, 2, 2, 2, 2, 2, 3 , 3, 3]) 作为未扩展因子的基本列表和扩展因子的列表。在每一轮中，我从基础中选择一个因子，减少它的数量，并将通过动态编程和截止策略，这变得非常快：
如果可以的话尝试 Psyco （我不能，因为我这里只有 Py2.7），它也可能会加快速度。
I use a list like
[(2, 9), (3, 3)](for[2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]) as the base list of unexpanded factors and a list of expanded factors. In each round I pick one factor from the base, decreasing it's count, andWith dynamic programming and the cutoff strategy this became extremely fast:
Try Psyco if you can (I cant because I only have Py2.7 here), it might speed this up quite a bit too.