I am a computer-science hobbyist and located an NP-complete drawback that’s just like each subset-product and Precise Cowl by 3-sets.
Right here, is a Discount of Precise-Cowl into my drawback. I’m multiplying all integers in units of C.
Enter previous to discount
s: [1, 2, 3, 4, 5, 6]
c: [[5, 2, 1], [6, 4, 3]]
Output after discount
s : [1, 2, 3, 4, 5, 6]
c : [10, 72]
Integers wanted for True subset-product
[[5, 2, 1], [6, 4, 3]]
Algorithm
import itertools
from itertools import mixtures
from itertools import permutations
import operator
from operator import mul
from functools import scale back
s = [1,2,3,4,5,6]
c = 10,72
# Getting ready all attainable
# three-element units
find_X_thr_covers=[];
for jj in permutations((s), 3):
if len(jj) == len(set(jj)):
# I'll "keep in mind" multiplied units in c for later use.
if scale back(mul, jj) in c:
find_X_thr_covers.append(jj)
# Right here, I'll use len(s)//Three mixtures
# for a particular case of the Precise Cowl
# drawback by 3-sets.
options = []
solutions_two = []
for jj in mixtures(find_X_thr_covers, len(s)//3):
# Right here I'll confirm that each attainable mixture
# is certainly a real resolution.
jj_flat = [item for sub in jj for item in sub]
jj_set = set(jj_flat)
if set(s) == jj_set and len(jj_set) == len(jj_flat):
resolution = listing(jj)
# I'll use a for loop to multiply all components in
# the Precise Three Cowl options.
for a in vary(0, len(resolution)):
resolution[a] = scale back(mul, resolution[a])
if a == len(resolution) - 1:
options.append(resolution)
solutions_two = jj
break
# eradicating repeating units
options =[solutions[x] for x in vary(len(options)) if not(options[x] in options[:x])]
print(options)
print(solutions_two)
print('Discovered Precise Three Product Cowl')
Output
[[10, 72], [72, 10]]
((5, 2, 1), (6, 4, 3))
Discovered Precise Three Product Cowl
Questions
Is utilizing mounted permutations of three a foul method to clear up this drawback?
What is the slowest elements of my python script and the way do I enhance execution pace with AlgorithimX?
Edit: The algorithimX is not essential to be supplied as an answer however ought to solely be defined if attainable in a pythonic method. I am wonderful with a solution that solely explains the issues with my code.