Quine–McCluskey algorithm

[vak]

На днях обсуждали со spamsink минимизацию булевских функций. Тема из далёкого студенчества. Задачка нетривиальная, но давно и глубоко проработанная. Озадачил нею Грока, получил два решения:

на Питоне: minimize-boolean-function.py

на Rust: minimize-boolean-function.rs

Функция с 8 переменными вычисляется на Rust за шесть секунд:

$ rustc minimize-boolean-function.rs

$ /usr/bin/time ./minimize-boolean-function 

Truth table: 0000000000X10000000000000000000000000000000000000000000000000000010X010X010X010X010X010X010X010X010X010X010X010X010X010X010X010X00000000001X0000000000000000000000000000000000001X1X1X1X1X1X1X1X0000000000000000000000000000000000000000000000000000000000000000
8-variable result: ~ABH + ~B~C~DE~FG + A~BCD
        6.26 real         6.22 user         0.03 sys