I have a running program. That accepts 1 to 15 variables The goal of the program was a simplifier. Based on the Quine–McCluskey algorithm
Consider 3 variables
000
001
010
011
100
101
110
111
I group them by number of 1
000
001
010
100
011
101
110
111
Then I compare each string from the group to the next group
group 1
000
group 2
001
010
100
group 3
011
101
110
group1 -> group2
------------------
000 -> 001 = 00-
000 -> 010 = 0-0
000 -> 100 = -00
------------------
group2 ->group3
--------------------
001 -> 011 = 0-1
001 -> 101 = -01
001 -> 110 = no output
010 -> 011 = 01-
010 -> 101 = no output
010 -> 110 = -10
100 -> 011 = no output
100 -> 101 = 10-
100 -> 110 = 1-0
---------------------
etc.
then group the output again by number of 1 and compare them again until no strings can be compared.
I need to achieve a 15 variable but it take for ever for the program to finish.Any Idea how to speed it up. I was testing it on threading but just a little improvement.
Number of Strings: 2048 Length of variable: 11 Time: 10 minutes
Need to Achieved
Number of Strings: 32767 Length of variable: 15 Time: cannot be achieved
List<List<string>> ImplicantsByOneFinal = new List<List<string>>();
List<List<string>> TermsByOne = new List<List<string>>();
is there a way or algorithm to improve this code. it becomes slower on 11 to 15 variables.
bool CombineAndGroup(List<List<string>> ImplicantsByOne)
{
TermsByOne = new List<List<string>>();
int combined = 0;
for (int i = 0; i < ImplicantsByOne.Count - 1; i++)
{
List<string> termsGrouped = new List<string>();
for (int j = 0; j < ImplicantsByOne[i].Count; j++)
{
int combination = 0;
int num1 = Convert.ToInt32((ImplicantsByOne[i][j]).Replace('-','0'), 2);
for (int k = 0; k < ImplicantsByOne[i + 1].Count; k++)
{
int num2 = Convert.ToInt32((ImplicantsByOne[i + 1][k]).Replace('-', '0'), 2);
int num3 = num2 - num1;
double num4 = Math.Log((double)num3, (double)2);
if (((num4 % 1) == 0) && (num3 > 0) && (Esum(ImplicantsByOne[i][j]) == Esum(ImplicantsByOne[i + 1][k])))
{
string combinedMinterm = CompareString(ImplicantsByOne[i][j], ImplicantsByOne[i + 1][k]);
if (!termsGrouped.Contains(combinedMinterm))
{
termsGrouped.Add(combinedMinterm);
}
}
}
}
if (termsGrouped.Count > 0)
{
combined += termsGrouped.Count;
}
TermsByOne.Add(termsGrouped);
}
return (combined > 0) ? true : false;
}
private int Esum(String binCode)
{
binCode = binCode.Replace('1','0');
binCode = binCode.Replace('-', '1');
int esum = Convert.ToInt32(binCode, 2);
return esum;
}
//Purpose of CompareString is to compare two string and change the unique char to '-'
//like 000 and 001 = 00-
private string CompareString(string str1, string str2)
{
if (str1 == str2)
{
CountCompareStringLoops++;
return str1;
}
else
{
if (str1.Length == 1)
{
return "-";
}
int halflength = str1.Length / 2;
return CompareString(str1.Substring(0, halflength), str2.Substring(0, halflength)) + CompareString(str1.Substring(halflength), str2.Substring(halflength));
}
}
Main Program
MintermsByOne = Loaded with string 000 001 and so on
CombineAndGroup(MintermsByOne);
ImplicantsByOneFinal = TermsByOne;
while (CombineAndGroup(TermsByOne))
{
ImplicantsByOneFinal = TermsByOne;
}
Output ImplicantsByOneFinal
