0
$\begingroup$

Let us define a set $\mathcal{S}=\{1,2, 3,\cdots,67\}$. I have a list of 132 subsets.

I want to obtain 16(or 17) mutually exclusive subsets such that union of such 16(or 17) is equal to $\mathcal{S}$.

In the case of 17 subsets, 2 subsets will have one element in common.

Here is the list of subsets

    SS={{1, 2, 32, 38}, {1, 2, 37, 38}, {1, 2, 32, 33}, {2, 3, 32, 33}, {2, 
  3, 38, 39}, {1, 2, 38, 39}, {2, 3, 33, 39}, {3, 4, 33, 34}, {2, 3, 
  33, 34}, {2, 3, 39, 40}, {3, 4, 39, 40}, {3, 4, 34, 40}, {3, 4, 40, 
  41}, {5, 6, 35, 44}, {5, 6, 43, 44}, {5, 6, 35, 36}, {6, 7, 35, 
  36}, {6, 7, 44, 45}, {5, 6, 44, 45}, {6, 7, 36, 45}, {6, 7, 45, 
  46}, {8, 9, 37, 38}, {8, 9, 38, 39}, {9, 10, 39, 47}, {9, 10, 38, 
  39}, {9, 10, 39, 40}, {10, 11, 39, 40}, {10, 11, 47, 48}, {10, 11, 
  40, 48}, {9, 10, 47, 48}, {10, 11, 48, 49}, {10, 11, 40, 41}, {11, 
  12, 48, 49}, {11, 12, 41, 49}, {11, 12, 40, 41}, {11, 12, 49, 
  50}, {11, 12, 41, 42}, {12, 13, 42, 50}, {12, 13, 49, 50}, {12, 13, 
  41, 42}, {12, 13, 42, 43}, {13, 14, 42, 43}, {13, 14, 43, 51}, {13, 
  14, 50, 51}, {12, 13, 50, 51}, {13, 14, 43, 44}, {13, 14, 51, 
  52}, {14, 15, 44, 52}, {14, 15, 51, 52}, {14, 15, 43, 44}, {14, 15, 
  52, 53}, {14, 15, 44, 45}, {15, 16, 45, 53}, {15, 16, 44, 45}, {15, 
  16, 52, 53}, {15, 16, 45, 46}, {15, 16, 53, 54}, {16, 17, 46, 
  54}, {16, 17, 53, 54}, {16, 17, 45, 46}, {18, 19, 47, 55}, {18, 19, 
  55, 56}, {18, 19, 47, 48}, {19, 20, 55, 56}, {19, 20, 47, 48}, {19, 
  20, 48, 56}, {19, 20, 56, 57}, {19, 20, 48, 49}, {20, 21, 49, 
  57}, {20, 21, 48, 49}, {20, 21, 56, 57}, {21, 22, 57, 58}, {20, 21, 
  57, 58}, {21, 22, 50, 58}, {20, 21, 49, 50}, {21, 22, 49, 50}, {21, 
  22, 58, 59}, {21, 22, 50, 51}, {22, 23, 58, 59}, {22, 23, 50, 
  51}, {22, 23, 51, 59}, {23, 24, 51, 52}, {22, 23, 51, 52}, {22, 23, 
  59, 60}, {23, 24, 52, 60}, {23, 24, 59, 60}, {24, 25, 53, 61}, {24, 
  25, 52, 53}, {23, 24, 52, 53}, {23, 24, 60, 61}, {24, 25, 60, 
  61}, {24, 25, 61, 62}, {24, 25, 53, 54}, {26, 27, 55, 56}, {26, 27, 
  56, 64}, {26, 27, 63, 64}, {26, 27, 64, 65}, {26, 27, 56, 57}, {27, 
  28, 64, 65}, {27, 28, 57, 65}, {27, 28, 56, 57}, {27, 28, 57, 
  58}, {28, 29, 57, 58}, {29, 30, 59, 66}, {28, 29, 58, 59}, {29, 30, 
  58, 59}, {29, 30, 59, 60}, {30, 31, 59, 60}, {30, 31, 60, 67}, {30, 
  31, 66, 67}, {29, 30, 66, 67}, {30, 31, 60, 61}, {1, 8, 37, 38}, {2,
   9, 38, 39}, {3, 10, 39, 40}, {4, 11, 40, 41}, {5, 14, 43, 44}, {6, 
  15, 44, 45}, {7, 16, 45, 46}, {10, 19, 47, 48}, {11, 20, 48, 
  49}, {12, 21, 49, 50}, {13, 22, 50, 51}, {14, 23, 51, 52}, {15, 24, 
  52, 53}, {16, 25, 53, 54}, {19, 26, 55, 56}, {20, 27, 56, 57}, {21, 
  28, 57, 58}, {22, 29, 58, 59}, {23, 30, 59, 60}, {24, 31, 60, 61}};
$\endgroup$
2
$\begingroup$

You can use LinearProgramming for this. The vector to be optimized is a selector of which subsets to include. The constraint is that each element is included at least once. So:

sol = LinearProgramming[
    ConstantArray[1,132],
    Transpose @ SparseArray[SparseArray[Thread[#->1], 67]& /@ SS],
    ConstantArray[{1,1}, 67],
    ConstantArray[{0,1},132],
    Integers
]

LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.

{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}

Check:

Total[%103]
Union @@ Pick[SS, sol, 1]
Length @ %

18

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67}

67

So, it seems you need at least 18 subsets.

Addendum

Here is a function that encapsulates the above approach:

SubsetCover[subsets:{__?VectorQ}] := Module[{indexed, boole, r, c},
    indexed = ArrayComponents[subsets];
    boole = Transpose @ SparseArray[SparseArray[Thread[#->1], 67]& /@ SS];
    {r, c} = Dimensions[boole];
    Quiet[
        LinearProgramming[
            ConstantArray[1, c],
            boole,
            ConstantArray[{1, 1}, r],
            ConstantArray[{0, 1}, c],
            Integers
        ],
        LinearProgramming::lpip
    ]
]

Your example:

SubsetCover[SS]

{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot. But, I do not understand why do we have 18 subsets chosen? $4\times 18=72$, but we have only 67 elements! is it not possible to put 17 as a constraint? $\endgroup$ – dipak narayanan May 21 '19 at 14:56
  • $\begingroup$ @dipaknarayanan I think it's because there is no way to have 17 subsets cover all of the elements. $\endgroup$ – Carl Woll May 21 '19 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.