Skip to content

Instantly share code, notes, and snippets.

@kotet kotet/qm.d
Created Jul 1, 2018

Embed
What would you like to do?
Quine-McCluskey algorithm
// (a & b) + (¬a & c) → [[T,T,X],[N,X,T]]
enum Literal
{
T, // Term
N, // ¬Term
X // Null
}
alias Conjunction = Literal[];
alias DNF = Conjunction[]; // Disjunctive normal form
DNF[] qm(DNF dnfin, size_t[] dontcare)
{
import std.algorithm : sort, uniq, any, fold, equal, filter, map, sum;
import std.range : array, iota, back, popBack, zip, empty;
size_t size = dnfin[0].length;
struct TaggedConjunction
{
bool flag;
size_t[] mergedfrom;
Conjunction conjunction;
}
TaggedConjunction[] merged;
TaggedConjunction[] prime;
foreach (i, c; dnfin)
merged ~= TaggedConjunction(false, [i], c);
do
{
auto table = new TaggedConjunction[][](size + 1);
foreach (c; merged)
table[hammingWeight(c.conjunction)] ~= c;
merged = [];
foreach (i; 0 .. size)
foreach (ref c1; table[i])
foreach (ref c2; table[i + 1])
if (hammingDistance(c1.conjunction, c2.conjunction) == 1)
{
auto mergedfrom = (c1.mergedfrom ~ c2.mergedfrom).sort.uniq.array();
auto mergedconjunction = merge(c1.conjunction, c2.conjunction);
merged ~= TaggedConjunction(false, mergedfrom, mergedconjunction);
c1.flag = true;
c2.flag = true;
}
foreach (t; table)
foreach (c; t)
if (c.flag == false && !any!(x => x == c)(prime))
prime ~= c;
}
while (merged != []);
size_t min = size_t.max;
DNF[] result;
bool[] stack = [false];
while (true)
{
if (stack.length < prime.length)
{
stack ~= false;
}
else
{
bool isCovered = zip(stack, prime).map!(x => (x[0]) ? x[1].mergedfrom : [])
.fold!((a, b) => a ~ b)
.sort
.uniq
.filter!(n => !any!(d => d == n)(dontcare))
.equal(iota(0, dnfin.length).filter!(n => !any!(d => d == n)(dontcare)));
if (isCovered)
{
auto tmp = zip(stack, prime).filter!(x => x[0])
.map!(x => x[1].conjunction)
.array;
size_t s = tmp.fold!((a, b) => a ~ b)
.map!(l => (l != Literal.X) ? 1 : 0)
.sum();
if (s < min)
{
min = s;
result = [tmp];
}
else if (s == min)
{
result ~= tmp;
}
}
while (!stack.empty && stack.back)
stack.popBack();
if (stack.empty)
return result;
stack.popBack();
stack ~= true;
}
}
}
unittest
{
// https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3%E3%83%BB%E3%83%9E%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AD%E3%83%BC%E6%B3%95
DNF input = () {
with (Literal)
return [// dfmt off
[N, T, N, N],
[T, N, N, N],
[T, N, N, T],// Don't care
[T, N, T, N],
[T, T, N, N],
[T, N, T, T],
[T, T, T, N],// Don't care
[T, T, T, T]
];
// dfmt on
}();
DNF[] output = () {
with (Literal)
return // dfmt off
[
[[X, T, N, N], [T, X, X, N], [T, X, T, X]], // B¬C¬D + A¬D + AC
[[X, T, N, N], [T, N, X, X], [T, X, T, X]] // B¬C¬D + A¬B + AC
];
// dfmt on
}();
assert(qm(input, [2, 6]) == output);
}
size_t hammingWeight(Conjunction a)
{
import std.algorithm : filter, map, sum;
return a.filter!(x => x == Literal.T)
.map!(x => 1)
.sum;
}
unittest
{
with (Literal)
{
assert(hammingWeight([N, N, N]) == 0);
assert(hammingWeight([N, N, T]) == 1);
assert(hammingWeight([T, T, T]) == 3);
assert(hammingWeight([X, N, T]) == 1);
}
}
size_t hammingDistance(Conjunction a, Conjunction b)
{
import std.algorithm : filter, map, sum;
import std.range : zip;
return zip(a, b).filter!(t => t[0] != t[1])
.map!(x => 1)
.sum;
}
unittest
{
with (Literal)
{
assert(hammingDistance([T, T, T], [T, T, T]) == 0);
assert(hammingDistance([N, N, N], [N, N, T]) == 1);
assert(hammingDistance([T, N, T], [N, T, N]) == 3);
assert(hammingDistance([T, N, X], [T, X, T]) == 2);
}
}
Conjunction merge(Conjunction a, Conjunction b)
{
assert(hammingDistance(a, b) == 1);
auto result = new Conjunction(a.length);
foreach (i, ref l; result)
if (a[i] == b[i])
{
l = a[i];
}
else
{
l = Literal.X;
}
return result;
}
unittest
{
with (Literal)
{
assert(merge([T, T, T], [T, T, N]) == [T, T, X]);
assert(merge([N, X, N], [N, X, T]) == [N, X, X]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.