The idea to use only itertools
with tuple (2,3,4) for example:
Have multiple cartesian products:
(2,),(3,),(4,) # repeat 1
(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4) # repeat 2
...
For each of this tuple, use reduce
with operator.mul
and starting value 1, to multiply them:
reduce(operator.mul, tuple, 1)
This will yield the multiplications for level 2 cartesian's product:
[reduce(operator.mul,t,3) for t in itertools.product((1,2,3),repeat=2)]
>>>[3, 6, 9, 6, 12, 18, 9, 18, 27]
Now, we need to increase repeat
until a stop condition is met, say: every multiplication will yield a result larger than the top
. Since the samllest value that counts is 2
(because 1
times 1
many times is just 1 so it wont count) we can multiply 2 times x while is lower than top
. So: top/2 = x
, means that we can iterate through range(1,top/2)
:
[reduce(operator.mul,t,1) for c in range(1,10/2) for t in itertools.product((1,2,3),repeat=2) if reduce(operator.mul, t, 1) < 10]
This will yield repeated values, so let's convert them in a set:
set([reduce(operator.mul,t,1) for c in range(1,10/2) for t in itertools.product((1,2,3),repeat=2) if reduce(operator.mul, t, 1) < 10])
Using only itertools
may be cumbersome for this, but the solution seems pretty. I'm sure it can be optimized by introducing a better stop condition. The final code would look like this:
NOTE: There's a theorem for prime numbers that will allow you to optimize the stop condition to math.sqrt(top)
import math
def f(t,m):
return set([reduce(operator.mul, t1, 1) for c in range(1,int(math.sqrt(m)) for t1 in itertools.product(t,repeat=c) if reduce(operator.mul,t1,1) < m])
f((2,3,4),10)
>>>set([2, 3, 4, 6, 8, 9])
Hope this might give you another idea :)