код
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
/// <summary>
/// Базовый класс для логических функций
/// </summary>
public abstract class LogicFunction
{
//Дизъюнкции или конъюнкции функции
public readonly ICollection<char[]> Terms = new LinkedList<char[]>();
//Вычисление значения функции
public abstract bool Calculate(bool[] X);
//Вычисление значения функции
public virtual bool Calculate(char[] X)
{
return Calculate(X.Select(p => p != '0').ToArray());
}
}
/// <summary>
/// Дизъюнктивная нормальная форма
/// </summary>
public class Dnf : LogicFunction
{
public override bool Calculate(bool[] X)
{
bool bResult = false;
foreach (char[] term in Terms)
{
bool TermVal = true;
for (int i = 0; i < term.Length; i++)
{
if (term[i] == '*') continue;
TermVal &= (term[i] != '0' ? X[i] : !X[i]);
}
bResult |= TermVal;
}
return bResult;
}
}
/// <summary>
/// Конъюнктивная нормальная форма
/// </summary>
public class Knf : LogicFunction
{
public override bool Calculate(bool[] X)
{
bool bResult = true;
foreach (char[] term in Terms)
{
bool TermVal = false;
for (int i = 0; i < term.Length; i++)
{
if (term[i] == '*') continue;
TermVal |= (term[i] != '0' ? X[i] : !X[i]);
}
bResult &= TermVal;
}
return bResult;
}
}
/// <summary>
/// Минимизация логической функции методом Квайна---Мак-Класки
/// </summary>
public class Quine_McCluskey
{
private readonly Dnf _result = new Dnf();
public Dnf Result
{
get { return _result; }
}
//Запуск метода
public void Start(IEnumerable<char[]> TermInput)
{
LogicFuncMinimize(TermInput, _result.Terms);
}
//Запуск метода
public void Start(string sFileName)
{
Start(LoadDsnfFromFile(sFileName));
}
//Нахождение минимальной логической функции
private static void LogicFuncMinimize(IEnumerable<char[]> X1, ICollection<char[]> OutR)
{
Dictionary<int, LinkedList<TreeNodeEnd>> OutTemp = new Dictionary<int, LinkedList<TreeNodeEnd>>();
if (X1.First().Length <= 40)
{
Dictionary<UInt64, TreeNodeEnd> X1Tree = new Dictionary<UInt64, TreeNodeEnd>();
DeleteDublicatingTerms(X1, X1Tree);
int iLevelCounter = 0;
//Повтор до тех пор пока будут оставаться термы
while (X1Tree.Count != 0)
{
Dictionary<UInt64, TreeNodeEnd> X2Tree = new Dictionary<UInt64, TreeNodeEnd>();
Skleivanie(X1Tree, X2Tree, OutTemp, iLevelCounter++);
X1Tree = X2Tree;
GC.Collect(); //Отсутствие сборки мусора очень сильно влияет на время работы!!!
}
}
else
{
TreeFuncTerm X1Tree = new TreeFuncTerm();
DeleteDublicatingTerms(X1, X1Tree);
int iLevelCounter = 0;
//Повтор до тех пор пока будут оставаться термы
while (X1Tree.Count != 0)
{
TreeFuncTerm X2Tree = new TreeFuncTerm();
Skleivanie(X1Tree, X2Tree, OutTemp, iLevelCounter++);
X1Tree = X2Tree;
GC.Collect(); //Отсутствие сборки мусора очень сильно влияет на время работы!!!
}
}
HashSet<TreeNodeEnd> OutRes = new HashSet<TreeNodeEnd>();
ReduceRedundancyTerms(OutTemp, OutRes);
OutR.Clear();
foreach (TreeNodeEnd term in OutRes) OutR.Add(term.Term);
}
//Процедура чтения ДСНФ из файла и запись в матрицу
private static ICollection<char[]> LoadDsnfFromFile(string sFullFileName)
{
ICollection<char[]> DSNF = new LinkedList<char[]>();
//Чтение строк из файла
using (StreamReader InFile = new StreamReader(sFullFileName))
{
string sLine = "";
while ((sLine = InFile.ReadLine()) != null)
{
DSNF.Add(sLine.ToArray());
}
}
return DSNF;
}
//Удаление дубликатов термов из входного списка
//В выходной словарь добавляются только уникальные термы
private static void DeleteDublicatingTerms(IEnumerable<char[]> InX1,
Dictionary<UInt64, TreeNodeEnd> OutX2Tree)
{
OutX2Tree.Clear();
TreeNodeEnd pCurrNode = null;
foreach (char[] x1 in InX1)
{
UInt64 iCode = GetTermCode(x1);
if (OutX2Tree.ContainsKey(iCode)) continue;
pCurrNode = new TreeNodeEnd(x1, null, null, pCurrNode, OutX2Tree.Count);
OutX2Tree.Add(iCode, pCurrNode);
}
}
//Удаление дубликатов термов из входного списка
//В выходное дерево добавляются только уникальные термы
private static void DeleteDublicatingTerms(IEnumerable<char[]> InX1, TreeFuncTerm OutX2Tree)
{
OutX2Tree.Clear();
foreach (char[] x1 in InX1)
{
OutX2Tree.AddTerm(x1, null, null);
}
}
//Склеивание строк с одним различием
private static void Skleivanie(TreeFuncTerm X1Tree, TreeFuncTerm X2Tree,
Dictionary<int, LinkedList<TreeNodeEnd>> OutResult, int iLevel)
{
LinkedList<TreeNodeEnd> OutR = new LinkedList<TreeNodeEnd>();
OutResult.Add(iLevel, OutR);
Dictionary<int, TreeNodeEnd> FindTerms = new Dictionary<int, TreeNodeEnd>();
TreeNodeEnd x1 = X1Tree.Last;
while (x1 != null)
{
X1Tree.SearchDiff1(x1, FindTerms);
if (FindTerms.Count == 0)
{
//Добавление на выход тех термов, которые ни с кем не склеились
OutR.AddLast(x1);
}
else
{
foreach (KeyValuePair<int, TreeNodeEnd> kvp in FindTerms)
{
//Проверка, чтобы комбинации термов обрабатывались только по одному разу
if (x1.Number < kvp.Value.Number) continue;
//Склеивание двух термов с одним различием
char cSymbSav = x1.Term[kvp.Key];
x1.Term[kvp.Key] = '*'; //Метка склеивания
X2Tree.AddTerm(x1.Term, x1, kvp.Value);
x1.Term[kvp.Key] = cSymbSav;
}
}
x1 = x1.Prev;
}
}
//Возвращает уникальный код для терма
private static UInt64 GetTermCode(char[] pTerm)
{
UInt64 iMultip = 1, iCode = 0;
for (int i = 0; i < pTerm.Length; i++)
{
switch (pTerm[i])
{
case '0':
break;
case '1':
iCode += iMultip;
break;
case '*':
iCode += (iMultip + iMultip);
break;
}
iMultip *= 3;
}
return iCode;
}
//Склеивание строк с одним различием
private static void Skleivanie(Dictionary<UInt64, TreeNodeEnd> X1Tree, Dictionary<UInt64,
TreeNodeEnd> X2Tree, Dictionary<int, LinkedList<TreeNodeEnd>> OutResult, int iLevel)
{
LinkedList<TreeNodeEnd> OutR = new LinkedList<TreeNodeEnd>();
OutResult.Add(iLevel, OutR);
foreach (KeyValuePair<UInt64, TreeNodeEnd> x1 in X1Tree)
{
bool bIsSkleiv = false;
UInt64 iMultip = 1;
for (int iPos = 0; iPos < x1.Value.Term.Length; iPos++)
{
char cSymbSav = x1.Value.Term[iPos];
if (cSymbSav != '*')
{
UInt64 iCode;
if (cSymbSav == '0')
iCode = x1.Key + iMultip;
else //_if (cSymbSav == '1')
iCode = x1.Key - iMultip;
TreeNodeEnd pSkleivNode = null;
X1Tree.TryGetValue(iCode, out pSkleivNode);
if (pSkleivNode != null)
{
bIsSkleiv = true;
//Проверка, чтобы комбинации термов обрабатывались только по одному разу
if (x1.Value.Number > pSkleivNode.Number)
{
//Склеивание двух термов с одним различием
if (cSymbSav == '0')
iCode = x1.Key + iMultip + iMultip;
else //_if (cSymbSav == '1')
iCode = x1.Key + iMultip;
x1.Value.Term[iPos] = '*'; //Метка склеивания
if (!X2Tree.ContainsKey(iCode)) X2Tree.Add(iCode,
new TreeNodeEnd(x1.Value.Term, x1.Value, pSkleivNode, null, X2Tree.Count));
x1.Value.Term[iPos] = cSymbSav;
}
}
}
iMultip *= 3;
}
if (!bIsSkleiv)
{
//Добавление на выход тех термов, которые ни с кем не склеились
OutR.AddLast(x1.Value);
}
}
}
// Отбрасывание избыточных терм с помощью алгоритма приближенного решения задачи о покрытии.
private static void ReduceRedundancyTerms(Dictionary<int, LinkedList<TreeNodeEnd>> X,
HashSet<TreeNodeEnd> ResultNumbers)
{
//Подготовка результирующего контейнера
ResultNumbers.Clear();
//Контейнер первичных входных термов с распределением по кол-ву образовавших выходные термы
HashSet<TreeNodeEnd> pNumbersForAdd = new HashSet<TreeNodeEnd>();
Dictionary<TreeNodeEnd, uint> Numbers2Terms = new Dictionary<TreeNodeEnd, uint>();
Dictionary<TreeNodeEnd, HashSet<TreeNodeEnd>> Terms2Numbers =
new Dictionary<TreeNodeEnd, HashSet<TreeNodeEnd>>();
//Формирование распределения по уровню
foreach (int iLevel in X.Keys.OrderByDescending(p => p).AsQueryable())
{
foreach (TreeNodeEnd term in X[iLevel])
{
HashSet<TreeNodeEnd> TermNumberCont = new HashSet<TreeNodeEnd>();
HashSet<TreeNodeEnd> ListNumbers = new HashSet<TreeNodeEnd>();
ListNumbers.Add(term);
while (ListNumbers.Count > 0)
{
TreeNodeEnd pCurrNode = ListNumbers.First();
ListNumbers.Remove(pCurrNode);
if (pCurrNode.Parent1 != null && pCurrNode.Parent2 != null)
{
ListNumbers.Add(pCurrNode.Parent1);
ListNumbers.Add(pCurrNode.Parent2);
}
else
{
if (!Numbers2Terms.ContainsKey(pCurrNode)) Numbers2Terms.Add(pCurrNode, 0);
Numbers2Terms[pCurrNode]++;
//Добавление номера в контейнер
TermNumberCont.Add(pCurrNode);
}
}
//int iIntersectNumbers = pNumbersForAdd.Intersect(TermNumberCont).Count();
//if (iIntersectNumbers < TermNumberCont.Count)
{
pNumbersForAdd.UnionWith(TermNumberCont);
Terms2Numbers.Add(term, TermNumberCont);
}
}
}
//Выполняется первый принцип - первыми обрабатываются минимальные столбцы ТП
pNumbersForAdd = new HashSet<TreeNodeEnd>(pNumbersForAdd.OrderBy(p => Numbers2Terms[p]));
//Контейнер для хранения отобранных выходных термов с их связями с входными
Dictionary<TreeNodeEnd, HashSet<TreeNodeEnd>> SelectedTerms =
new Dictionary<TreeNodeEnd, HashSet<TreeNodeEnd>>();
//Перебор всех первичных входных термов
while (pNumbersForAdd.Count > 0)
{
//Проверяемый входной терм
TreeNodeEnd pSrcTerm = pNumbersForAdd.First();
//Отбор лучшего выходного терма, который был образован с участием данного входного терма
TreeNodeEnd BestTerm = null;
int iBestTermNumbersCount = 0;
foreach (KeyValuePair<TreeNodeEnd, HashSet<TreeNodeEnd>> CurrTerm in Terms2Numbers)
{
if (!CurrTerm.Value.Contains(pSrcTerm)) continue;
int iCurrTermNumbersCount = CurrTerm.Value.Intersect(pNumbersForAdd).Count();
if ((BestTerm == null) || (iBestTermNumbersCount < iCurrTermNumbersCount))
{
BestTerm = CurrTerm.Key;
iBestTermNumbersCount = iCurrTermNumbersCount;
}
}
ResultNumbers.Add(BestTerm);
HashSet<TreeNodeEnd> pBestTermSrcNodes = Terms2Numbers[BestTerm];
Terms2Numbers.Remove(BestTerm);
SelectedTerms.Add(BestTerm, pBestTermSrcNodes);
pNumbersForAdd.RemoveWhere(p => pBestTermSrcNodes.Contains(p));
}
//Чтобы освободить неиспользуемую память
Terms2Numbers = SelectedTerms;
//Теперь проверка на возможность выкинуть из списка отобранных
TreeNodeEnd termForDelete = null;
do
{
termForDelete = null;
int iTermForDeleteUsedNumbCount = 0;
foreach (KeyValuePair<TreeNodeEnd, HashSet<TreeNodeEnd>> term1 in SelectedTerms)
{
int iUsedNumbCounter = 0;
foreach (TreeNodeEnd numb in term1.Value)
{
bool bFind = false;
foreach (KeyValuePair<TreeNodeEnd, HashSet<TreeNodeEnd>> term2 in SelectedTerms)
{
if (term1.Key == term2.Key) continue;
if (bFind = term2.Value.Contains(numb)) break;
}
if (bFind) iUsedNumbCounter++;
}
if ((iUsedNumbCounter == term1.Value.Count) && ((termForDelete == null) ||
(iUsedNumbCounter <= iTermForDeleteUsedNumbCount)))
{
termForDelete = term1.Key;
iTermForDeleteUsedNumbCount = iUsedNumbCounter;
}
}
if (termForDelete != null)
{
ResultNumbers.Remove(termForDelete);
SelectedTerms.Remove(termForDelete);
}
} while (termForDelete != null);
}
}
/// <summary>
/// Дерево термов
/// </summary>
public class TreeFuncTerm
{
//Корень
private readonly TreeNodeMiddle rootNode = new TreeNodeMiddle();
//Ссылка на завершающий узел последовательности ссылок на конечные листья дерева
private TreeNodeEnd _lastTreeNode = null;
public TreeNodeEnd Last
{
get { return _lastTreeNode; }
}
//Возвращает количество термов в дереве
private int _count = 0;
public int Count
{
get { return _count; }
}
//Конструктор
public TreeFuncTerm()
{
Clear();
}
//Очистить дерево
public void Clear()
{
rootNode.Clear();
_count = 0;
_lastTreeNode = null;
}
//Добавление в дерево нового терма
public void AddTerm(char[] term, TreeNodeEnd pParent1, TreeNodeEnd pParent2)
{
TreeNodeMiddle pCurrNode = rootNode;
for (int j = 0; j < term.Length; j++)
{
TreeNodeBase item = pCurrNode.GetChild(term[j]);
if (item == null)
{
if (j + 1 < term.Length)
{
item = new TreeNodeMiddle();
}
else
{
item = new TreeNodeEnd(term, pParent1, pParent2, _lastTreeNode, _count);
_lastTreeNode = (TreeNodeEnd)item;
_count++;
}
pCurrNode.AddChild(item, term[j]);
}
if (item is TreeNodeMiddle) pCurrNode = (TreeNodeMiddle)item;
}
}
//Поиск последовательностей с одним отличием от заданной не рекурсивным способом
public void SearchDiff1(TreeNodeEnd x1, Dictionary<int, TreeNodeEnd> result)
{
result.Clear();
TreeNodeMiddle pCurrNode = rootNode;
Dictionary<int, TreeNodeMiddle> OneDiffNodesList = new Dictionary<int, TreeNodeMiddle>();
for (int iPos = 0; iPos < x1.Term.Length; iPos++)
{
char cSymbol = x1.Term[iPos];
if (pCurrNode != null)
{
if (cSymbol != '*')
{
TreeNodeBase item = pCurrNode.GetChild(cSymbol == '0' ? '1' : '0');
if (item != null)
{
if (item is TreeNodeMiddle)
{
OneDiffNodesList.Add(iPos, (TreeNodeMiddle)item);
}
else //if (item is TreeNodeEnd)
{
//Добавление терма в выходной список
result.Add(iPos, (TreeNodeEnd)item);
}
}
}
TreeNodeBase pNextNode = pCurrNode.GetChild(cSymbol);
if ((pNextNode != null) && (pNextNode is TreeNodeMiddle))
{
pCurrNode = (TreeNodeMiddle)pNextNode;
}
}
//Проверяются последовательности, отобранные на предыдущих позициях,
//на единственность отличия от заданной
for (int iKey = 0; iKey < iPos; iKey++)
{
if (!OneDiffNodesList.ContainsKey(iKey)) continue;
TreeNodeMiddle pValue = OneDiffNodesList[iKey];
TreeNodeBase item = pValue.GetChild(cSymbol);
if (item == null)
{
OneDiffNodesList.Remove(iKey);
}
else if (item is TreeNodeMiddle)
{
OneDiffNodesList[iKey] = (TreeNodeMiddle)item;
}
else //if (item is TreeNodeEnd)
{
//Добавление терма в выходной список
result.Add(iKey, (TreeNodeEnd)item);
}
}
}
}
}
/// <summary>
/// Базовый интерфейс узла дерева термов
/// </summary>
public interface TreeNodeBase
{
//Очистка выделенных ресурсов
void Clear();
}
/// <summary>
/// Конечный узел дерева термов
/// </summary>
public class TreeNodeEnd : TreeNodeBase
{
//Терм, сопоставленный узлу
private char[] _term;
public char[] Term
{
get { return _term; }
}
//Ссылка на предыдущий конечный узел дерева текущего уровня для одностороннего связанного списка
private TreeNodeEnd _prev;
public TreeNodeEnd Prev
{
get { return _prev; }
}
//Ссылка на родительский конечный узел дерева предыдущего уровня
private TreeNodeEnd _parent1;
public TreeNodeEnd Parent1
{
get { return _parent1; }
}
//Ссылка на родительский конечный узел дерева предыдущего уровня
private TreeNodeEnd _parent2;
public TreeNodeEnd Parent2
{
get { return _parent2; }
}
//Номер узла, который он имеет в последовательности всех конечных узлов текущего уровня
public readonly int Number;
//Конструктор
public TreeNodeEnd(char[] pTermRef, TreeNodeEnd pParent1, TreeNodeEnd pParent2,
TreeNodeEnd pPrevTreeNode, int iNumber)
{
pTermRef.CopyTo(_term = new char[pTermRef.Length], 0);
_parent1 = pParent1;
_parent2 = pParent2;
_prev = pPrevTreeNode;
Number = iNumber;
}
//Очистка выделенных ресурсов
public void Clear()
{
_term = null;
_parent1 = null;
_parent2 = null;
_prev = null;
}
}
/// <summary>
/// Промежуточный узел дерева термов
/// </summary>
public class TreeNodeMiddle : TreeNodeBase
{
//Дочерние узлы
private TreeNodeBase Childs0;
private TreeNodeBase Childs1;
private TreeNodeBase Childs2;
//Очистка выделенных ресурсов
public void Clear()
{
if ((Childs0 != null) && (Childs0 is TreeNodeMiddle)) ((TreeNodeMiddle)Childs0).Clear();
if ((Childs1 != null) && (Childs1 is TreeNodeMiddle)) ((TreeNodeMiddle)Childs1).Clear();
if ((Childs2 != null) && (Childs2 is TreeNodeMiddle)) ((TreeNodeMiddle)Childs2).Clear();
Childs0 = Childs1 = Childs2 = null;
}
//Получение дочернего узла
public TreeNodeBase GetChild(char cSymbol)
{
switch (cSymbol)
{
case '0':
return Childs0;
case '1':
return Childs1;
case '*':
return Childs2;
}
return null;
}
//Добавление дочернего узла
public void AddChild(TreeNodeBase newChild, char cSymbol)
{
switch (cSymbol)
{
case '0':
Childs0 = newChild;
break;
case '1':
Childs1 = newChild;
break;
case '*':
Childs2 = newChild;
break;
}
}
}