Styjun

Hello guys here is the problem. I have something like this in input [[1,2,3],[4,5,6],[7,8,9]]...etc

And i want to generate all possible combination of product of those list and then multiply each elements of the resulting combination beetween them to finally filter the result in a interval.

So first input a n list [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]...etc

Which will then give (1,4,7,10)
(1,4,7,11)
(1,4,7,12)
and so on

Then combination of those result for k in n like (1,4,7)(1,4,10)(1,7,10) for the first row

The multiplication of x as 1*4*7 = 28, 1*4*10 = 40, 1*7*10 = 70

And from this get only the unique combination and the result need in the interval choosed beforehand : if x > 50 and x < 100 i will get (1,7,10) : 70

I did try

 def mult(lst): #A function mult i'm using later
 r = 1
 for element in lst:
 r *= element
 return round(r)

 s = [] #Where i add my list of list
 for i in range(int(input1)):
 b = input("This is line %s : " % (i+1)).split()
 for i in range(len(b)):
 b[i] = float(b[i]) 
 s.append(b)

 low_result = input("Expected low_result : ")
 high_result = input("Expected high_result : ")

 combine = []
 my_list = []

 for element in itertools.product(*s):
 l= [float(x) for x in element]
 comb = itertools.combinations([*l], int(input2))
 for i in list(comb):
 combine.append(i)
 res = mult(i)
 if res >= int(low_result) and res <= int(high_result):
 my_list.append(res) 
 f = open("list_result.txt","a+")
 f.write("%s : result is %sn" % (i, res))
 f.close()

And it always result in memory error cause there is too many variation with what i'm seeking.

What i would like is a way to generate from a list of list of 20 elements or more all the product and resulting combination of k in n for the result(interval) that i need.

As suggested above, I think this can be done without exploding your memory by never holding an array in memory at any time. But the main issue is then runtime.

The maths

As written we are:

• Producing every combination of m rows of n items n ** m
  


• Then taking a choice of c items from those m values C(m, c)

This is very large. If we have m=25 rows, of n=3 items each and pick c=3 items in them we get:

• = n ** m * C(m, c)


• 
  = 3 ** 25 * 2300 - n Choose r calculator
  


• = 1.948763802×10¹⁵

If instead we:

• Choose c rows from the m rows: C(m, c) as before


• Then pick every combination of n items from these c rows: n ** c

With m=25 rows, of n=3 items each and pick c=3 items in them we get:

• = n ** c * C(m, c)
  


• = 3 ** 3 * 2300
  


• = 20700
  

This is now a solvable problem.

The code

from itertools import product, combinations


def mult(values, min_value, max_value):
 """
 Multiply together the values, but return None if we get too big or too
 small
 """
 output = 1

 for value in values:
 output *= value

 # Early return if we go too big
 if output > max_value:
 return None

 # Early return if we goto zero (from which we never return)
 if output == 0 and min_value != 0:
 return None

 if output < min_value:
 return None

 return output


def yield_valid_combos(values, choose, min_value, max_value):
 # No doubt an even fancier list compression would get this too
 for rows in combinations(values, choose):
 for combos in product(*rows):
 value = mult(combos, min_value, max_value)

 if value is not None:
 yield combos, value


values = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]


with open('list_result.txt', 'w') as fh:
 for selection, value in yield_valid_combos(
 values, choose=3, min_value=50, max_value=100):
 fh.write(': result is n'.format(selection, value))

This solution also returns no duplicate answers (unless the same value appears in multiple rows).

As an optimisation the multiplication method attempts to return early if we detect the result will be too big or small. We also only open the file once and then keep adding rows to it as they come.

Further optimisation

You can also optimise your set of values ahead of time by screening out values which cannot contribute to a solution. But for smaller values of c, you may find this is not even necessary.

The smallest possible combination of values is c items from the set of the smallest values in each row. If we take the c - 1 smallest items from the set of smallest values, mutliply them together and then divide the maximum by this number, it gives us an upper bound for the largest value which can be in a solution. We can then then screen out all values above this value (cutting down on permutations)