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

Comments

[vak]

Улучшенная версия на Rust справляется за 0.2 секунды:
https://github.com/sergev/vak-opensource/blob/master/languages/rust/qmc/src/minimizer.rs

Правда, имена переменных печатает неправильно, не с того конца.