1
$\begingroup$

I have a set of binary vectors that I would like to group into a minimal number of sets. A set can be formed when it contains all combinations of elements that vary within that set.

Example: for {1011,1001,1010,1000, 0001}, two ways to group the vectors are the following:

{1011,1001,1010,1000} and {0001}

OR

{1011},{1010,1000}, and {1001,0001}

In the first case, the first set has all the combinations of elements 3 and 4. In the second case the second set has all the combinations of elements 3, and the third set of element 1. One- and Two-member sets are pretty trivial, and all sets will contain a power of 2 number of elements, since the variables are binary.

Because I am looking for the minimal number of sets, I would prefer the first option. Is there an algorithm that calculates this minimal number of sets? Surely this problem has already been answered.

Thank you!

$\endgroup$
6
$\begingroup$

This problem is well known as the Karnaugh tables problem. It is a NP problem. Some algorithms are been studied for electronic industry. A example of implementation is the old software named "espresso" (free, algorithm documented). There is (are?) also such algorithm (s) in Mathematica. I don' t know if the implementation of "espresso" is inside.

There is a detail that may make you question a variant from the original problem : You want to minimize the number of subsets, but do you want the subsets to be disjoint? That is to say do you prefer the couple {1011, 1001, 1010, 1000} {0001} to the couple {1011, 1001, 1010, 1000} {1001, 0001}. It depends on your context. In most cases (boolean equations minimization for example), the later is better.

The first solution hereafter is the one that gives {1011, 1001, 1010, 1000} {1001, 0001} It is simplest solution. After that I propose a "solution" that gives {1011, 1001, 1010, 1000} {0001}, but in that case the subsets are not necesseraly "hypercube" (that is to say some elements that takes all combinations, and the other are the same, as you describe in your question). The idea is simply to remove the common elements of the subsets (that can destroy the hypercubes property)

solution 1 (which gives : {1011, 1001, 1010, 1000} {1001,0001})

ti01 = IntegerDigits[{1011, 1001, 1010, 1000, 0001}, 10, 4];
Clear[a];
varList = Table[a[i], {i, 1, Length[ti01[[1]]]}];
ti02 = BooleanMinterms[ti01, varList]
(* In the present case, the following line is useless because BooleanMinterms as already done the job *)
ti03 = BooleanMinimize[ti02, "SOP", Method -> {MaxIterations -> Infinity , Method -> Automatic (* not documented *)}]
ti04 = List @@ ti03
SatisfiabilityInstances[#, varList, All] & /@ ti04 /. {True -> 1, False -> 0} 

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

solution 2 (which gives : {1011, 1001, 1010, 1000} {0001})

ti01 = IntegerDigits[{1011, 1001, 1010, 1000, 0001}, 10, 4];
Clear[a];
varList = Table[a[i], {i, 1, Length[ti01[[1]]]}];
ti02 = BooleanMinterms[ti01, varList];  

(* In the present case, the following line is useless because BooleanMinterms    
 as already done the job *)
ti03 = BooleanMinimize[ti02, "SOP", Method -> {MaxIterations -> Infinity , Method -> Automatic (* not documented *)}];  

ti04 = List @@ ti03;  

(* Hereafter : elimination of the elements common to several subsets *)
(* The test Length[...] places the more general expressions, corresponding the bigger   
subsets, at the beginning *)
ti05 = SortBy[ti04, Length[BooleanVariables[#]] &];
ti06 = FoldList[Append, {First[ti05]}, Rest[ti05]]; 

(* scan the list of boolean equations from left to right, and modify 
them so that the cases already encountered are excluded, this may destroy the hypercube property *)
ti07 = And[Not[Or @@ Most[#]], Last[#]] & /@ ti06;  

(* find the vectors *)
SatisfiabilityInstances[#, varList, All] & /@ ti07 /. {True -> 1, False -> 0}  

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

$\endgroup$
  • $\begingroup$ Thank you! This solved the question perfectly. $\endgroup$ – Hybrid Mar 28 '16 at 18:40

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.