how to find the shortest products of randomly removed complete product?
(2, 2, 2, 2)
(2, 2, 2, 1)
(2, 2, 1, 2)
(2, 2, 1, 1)
(2, 1, 2, 2)
(2, 1, 2, 1)
(2, 1, 1, 2)
(2, 1, 1, 1)
(1, 2, 2, 2)
(1, 2, 2, 1)
(1, 2, 1, 2)
(1, 2, 1, 1)
(1, 1, 2, 2)
(1, 1, 2, 1)
(1, 1, 1, 2)
(1, 1, 1, 1)
above is the product of [(1,2), (1,2), (1,2), (1,2)], length of product = 1, this is also called a complete product
elements in total: 16
now randomly a few of them get removed.
(2, 2, 2, 2)
(2, 2, 2, 1) -- removed
(2, 2, 1, 2)
(2, 2, 1, 1)
(2, 1, 2, 2) -- removed
(2, 1, 2, 1)
(2, 1, 1, 2)
(2, 1, 1, 1)
(1, 2, 2, 2)
(1, 2, 2, 1) -- removed
(1, 2, 1, 2)
(1, 2, 1, 1)
(1, 1, 2, 2)
(1, 1, 2, 1) -- removed
(1, 1, 1, 2)
(1, 1, 1, 1)
now we have:
(2, 2, 2, 2)
(2, 2, 1, 2)
(2, 2, 1, 1)
(2, 1, 2, 1)
(2, 1, 1, 2)
(2, 1, 1, 1)
(1, 2, 2, 2)
(1, 2, 1, 2)
(1, 2, 1, 1)
(1, 1, 2, 2)
(1, 1, 1, 2)
(1, 1, 1, 1)
way 1
product of
[(1,), (1,2), (1,), (1,2)] + [(1,2), (2,), (2,), (2,)] + [(2,), (1,2), (1,), (1,2)]
add
(1, 1, 2, 2)
(2, 1, 2, 1)
the length of product = 5, so we shorten 12 to 5
way 2
we have anther way to shorten it:
product of
[(1,2), (1,2), (1,), (1,)] + [(1,2), (2,), (1,2), (2,)] + [(1,), (1,), (1,2), (2,)]
add
(2, 1, 2, 1)
(2, 1, 1, 2)
the length of product = 5, so we shorten 12 to 5
these two ways have different products but the same length.
So there should exist a best shortening way that could shorten 12 to minimal.
In general, we have a complete product, and randomly some of its element are removed, we want to find the smallest product in length or the best way to shorten it.
Any thoughts or information would help.
You can solve this as a set covering problem. Let $I$ be the set of points to cover, and let $P$ be the set of products. For $i\in I$, let $P_i\subseteq P$ be the set of products that contain $i$. For $p\in P$, let binary decision variable $x_p$ indicate whether product $p$ is selected. The problem is to minimize $\sum_p x_p$ subject to $$\sum_{p\in P_i} x_p \ge 1 \quad \text{for all $i\in I$}$$
For your example, $|I|=12$, $|P|=39$, and the minimum is $4$: $$[1,(1,2),(1,2),2]+[2,1,(1,2),1]+[(1,2),2,(1,2),2]+[(1,2),(1,2),1,(1,2)]$$