This program works approximately the same as Version 3 and not as good as Version 4. When it was first written it was believed to be superior to Version 3 and I thought it was the only version that was correct. Later I discovered it had some mistakes. But now those mistakes are fixed-- I am still looking for more mistakes. The program below works perfectly, you can copy and run. This is the version with: permutator, repeating variable, and threshold. The ratio is 0.571.
import java.io.*;
import static java.lang.Math.*;
import java.util.*;
public class QSATsolver6 {
private int clausesize = 3;
private int numvariable = 7; //crashes for 10 variable
private int numclause = 4;
private int numinstances = 50;
private ArrayList<Integer> temp2var = new ArrayList <Integer> ();
private ArrayList<ArrayList <Integer>> temp5var = new ArrayList <ArrayList<Integer>> ();
private ArrayList<String> chain = new ArrayList<String>();
private ArrayList<String> stack = new ArrayList<String>();
private ArrayList<double[][]> piMatrixStack = new ArrayList<double[][]>();
private ArrayList<double[][]> realStack = new ArrayList<double[][]>();
private ArrayList<ArrayList<Double>> temp2 = new ArrayList<ArrayList<Double>>();
private ArrayList<ArrayList<ArrayList<Double>>> temp5 = new ArrayList<ArrayList<ArrayList<Double>>>();
private ArrayList<Double>temp = new ArrayList<Double>();
private int netCount = 0;
private int counter3=0;
private double threshold=0.0055;
private static final double Epsilon = 1e-10;
public static void main(String[] args) {
QSATsolver6 qs = new QSATsolver6();
qs.generate();
}
public void generate(){
double length = 0;
int max = (int)pow(2,numvariable);
boolean []taken = new boolean [numvariable];
for(int i=0; i<taken.length; i++){
taken[i] = false;
}
for (int k = 0; k < numinstances; k++) {
for (int j = 0; j < numclause; j++) {
int v;
int same= 0;
ArrayList<Integer> list5= new ArrayList<Integer>();
for(int i = 0; i < clausesize; i++){
v = (int)(Math.random()*numvariable)+1;
if (taken[v-1] == true){
same++;
} else{
list5.add(new Integer(v));
}
taken[v-1] = true;
temp2var.add(new Integer(v));
}
int max2 = (int)pow(2,list5.size());
for (int i = 0; i < max2; i++){
/*String temp3 = Tobinary(i,"");
temp3 = reverseString(temp3);
if (temp3.length()<numclause) {
temp3 = addZero(temp3, numclause);
}
boolean valid= true;
ArrayList<Integer> stackvar2= new ArrayList<Integer>();
for(int p=0; p<list5.size();p++){
int a= Integer.parseInt(""+list5.get(p));
for(int y=0; y<temp2var.size(); y++){
int b= temp2var.get(y);
if(a==b){
stackvar2.add(new Integer(y));
}
}
double real, imaginary;
for(int z=0; z<stackvar2.size(); z++){
if(temp3.charAt(stackvar2.get(z))!=temp3.charAt(stackvar2.get(0))) {
valid= false;
break;
}
}
if(!valid){
real = 0;
imaginary = 0;
temp.add(new Double(real));
temp.add(new Double(imaginary));
break;
}
else {
real = Math.random();
imaginary = Math.random();
int sign = (int)(Math.random()*2);
temp.add(new Double(real));
if (sign == 0){
temp.add(new Double(-1*imaginary));
}
else {
temp.add(new Double(imaginary));
}
}
stackvar2= new ArrayList<Integer>();
}*/
double real = Math.random();
temp.add(new Double(real));
temp2.add(temp);
temp = new ArrayList<Double>();
}
for(int i = 0; i < taken.length; i++){
taken[i] = false;
}
for (int i = 0; i < temp2.size(); i++){
ArrayList <Double> list = temp2.get(i);
for (int g = 0; g < list.size(); g++){
double a = Double.parseDouble(""+list.get(g));
length += a;
}
}
for (int i = 0; i < temp2.size(); i++){
ArrayList <Double> list = temp2.get(i);
for (int g = 0; g < list.size(); g++){
double c = Double.parseDouble(""+list.get(g));
c = c/length;
list.remove(g);
list.add(g, new Double(c));
}
}
temp5.add(temp2); //15 items in these
temp2 = new ArrayList<ArrayList<Double>>(); //8 items
temp5var.add(temp2var);
temp2var = new ArrayList <Integer> ();
//chain = new ArrayList<String>();
length=0;
}
makeAllClauses();
if(calculateMatrix()){
netCount++;
}
piMatrixStack = new ArrayList<double[][]>();
realStack = new ArrayList<double[][]>();
temp5var = new ArrayList <ArrayList<Integer>> ();
temp5 = new ArrayList<ArrayList<ArrayList<Double>>>();
System.out.println(counter3);
counter3=0;
}
System.out.println(netCount);
}
public boolean calculateMatrix(){
double[][] temp1, temp2;
int max = (int)pow(2,numvariable);
double [][]sumtemp1 = new double [max][max];
boolean success = false;
for(int i=0; i<piMatrixStack.size(); i++){
double[][] one = piMatrixStack.get(i);
double[][] two = realStack.get(i);
/*for(int j=0; j<two.length; j++) {
for(int k=0; k<two.length; k++) {
System.out.print(two[j][k]+" ");
}
System.out.println("");
}*/
double[][] invone = makeTranspose(one);
temp1 = matMultiply(matMultiply(one,two), invone);
for(int j = 0; j < temp1.length; j++){
for(int k = 0; k < temp1.length; k++){
sumtemp1[j][k] += temp1[j][k];
}
}
}
/*for(int j = 0; j < sumtemp1.length; j++){
for(int k = 0; k < sumtemp1.length; k++){
System.out.print(sumtemp1[j][k]+" ");
}
System.out.println("");
}
System.out.println("");
System.out.println("");*/
boolean [] x= gaussianElimination(sumtemp1);
/*for(int j = 0; j < sumtemp1.length; j++){
for(int k = 0; k < sumtemp1.length; k++){
System.out.print(sumtemp1[j][k]+" ");
}
System.out.println("");
}*/
success = nullvecExist(x);
return success;
}
public boolean nullvecExist(boolean [] x){
for(int i=0; i<x.length; i++){
if(x[i]==true){
//System.out.print(i+" ");
counter3++;
}
}
for(int i=0; i<x.length; i++){
if(x[i]==true){
return true;
}
}
return false;
}
public void swaprows(double[][]matrix){
//int zerocount = 0;
int max = matrix.length;
double [] temp;
int current = 0;
double ratio = 1;
boolean found = false;
//current is the line number you have just fixed.
//i is all the line numbers that you are working on still.
//the point of this part is to order rows by increasing zero count.
/*for(int i=0; i<max; i++){
System.out.print(zeroCount2(matrix[i])+" ");
}*/
current=0;
int currentCount=0;
while(current<max){
for(int i = current; i < max; i++){
if(zeroCount2(matrix[i]) == currentCount){
temp = matrix[i];
matrix[i] = matrix[current];
matrix[current] = temp;
current++;
}
}
currentCount++;
}
}
public void swaprows2 (double [][] matrix, int one, int two){
double[] temp;
temp = matrix[one];
matrix[one] = matrix[two];
matrix[two] = temp;
}
public boolean [] gaussianElimination(double [][]matrix){
int max = matrix.length;
double ratio = 1;
boolean [] sol= new boolean [max];
swaprows(matrix);
int ind=0;
int oldind=ind;
int count = zeroCount2(matrix[ind]);
while(ind+1<max){
int holdon=ind;
//partial pivoting
for(int i = ind+1; i<max; i++){
int c = zeroCount2(matrix[i]);
if(c==count) {
if(Math.abs(matrix[i][count])>Math.abs(matrix[ind][count]))
holdon=i;
} else if(c>count){
swaprows2(matrix,holdon,ind);
break;
}
}
for(int i = ind+1; i<max; i++){
int c = zeroCount2(matrix[i]);
if(c==count) {
ratio = matrix[i][count]/matrix[ind][count];
for(int w = 0; w < matrix.length; w++){
matrix[i][w]-=matrix[ind][w]*ratio;
}
} else if(c>count){
break;
}
}
swaprows(matrix);
for(int i=1; i<max; i++){
if(zeroCount2(matrix[i])==zeroCount2(matrix[i-1])){
ind=i-1;
break;
}
if(i==max-1){
ind=max-1;
}
}
count=zeroCount2(matrix[ind]);
if(count==max){
break;
}
}
for(int i=0; i<sol.length; i++){
sol[i]=true;
}
for(int i=0; i<matrix.length; i++){
if(Math.abs(matrix[i][i])>threshold){
sol[i]=false;
}
}
return sol;
}
public int zeroCount2 (double[] vec){
int temp = 0;
for(int i = 0; i < vec.length; i++){
if(vec[i]==0){
temp++;
} else{
break;
}
}
return temp;
}
public double[][] makeTranspose(double[][] mat){
double [][]temp = new double[mat.length][mat.length];
for(int i = 0; i < mat.length; i++){
for(int j = 0; j<mat[0].length; j++){
temp[i][j] = mat[j][i];
}
}
return temp;
}
public void makePi(){
int max = (int)pow(2,numvariable);
for(int j = 0; j<max; j++) {
String temp3 = Tobinary(j,"");
temp3 = reverseString(temp3);
if (temp3.length()<numvariable) {
temp3 = addZero(temp3, numvariable);
}
chain.add(temp3);
}
}
public void makeAllClauses(){
int max = (int)pow(2,numvariable);
int[] temp1;
int[] temp3;
boolean[] taken = new boolean[numvariable];
String takenstring="";
int[] path = new int[numvariable];
for(int i = 0; i < taken.length; i++){
taken[i] = false;
}
//int max2 = (int)pow(2,clausesize);
for(int i = 0; i<temp5var.size(); i++){
ArrayList<Integer> alist = temp5var.get(i); //temp2var list of 3 integers
ArrayList<ArrayList<Double>> blist = temp5.get(i); //temp2 8 items each
for(int j = 0; j < alist.size(); j++){
int temp2 = (int)(Integer.parseInt(""+alist.get(j)))-1;
if(!taken[temp2]) {
//temp1[j] = temp2;
Integer b= new Integer(temp2);
takenstring+=b;
takenstring+=" ";
taken[temp2] = true;
}
}
String []tokens = takenstring.split(" ");
temp1= new int[tokens.length];
takenstring="";
for(int l=0; l<temp1.length; l++){
temp1[l]=Integer.parseInt(tokens[l]);
//System.out.print(temp1[l]+" ");
}
//System.out.println();
int ind = 0;
temp3= new int[numvariable-temp1.length];
for(int j = 0; j < (numvariable); j++){
if(!taken[j]){
temp3[ind] = j;
//System.out.print(temp3[ind]+" ");
ind++;
}
}
//System.out.println();
for(int j = 0; j < taken.length; j++){
taken[j] = false;
}
for(int j = 0; j < numvariable; j++){
if(j<temp1.length){
path[j] = temp1[j];
}else {
path[j] = temp3[j-temp1.length];
}
}
/*for(int s=0; s<path.length; s++){
System.out.print(path[s]+" ");
}
System.out.println();*/
double[][] onePi = makeProjector(path,i);
piMatrixStack.add(onePi);
double [][]oneClause=new double[max][max];
for(int u=0; u<blist.size(); u++){
ArrayList<Double> list3= blist.get(u);
double factor= Double.parseDouble(""+list3.get(0));
String str2 = Tobinary(u,"");
str2 = reverseString(str2);
if (str2.length()<tokens.length) {
str2 = addZero(str2, tokens.length);
}
String str = getI(tokens.length)+""+reverseString(str2);
double[][]one = makeSig(str);
for(int l=0; l<one.length; l++){
for(int m=0; m<one.length; m++){
oneClause[l][m]+=factor*one[l][m];
}
}
}
double length=0;
for(int p=0; p<oneClause.length; p++){
length+=oneClause[p][p];
}
for(int p=0; p<oneClause.length; p++){
oneClause[p][p]=oneClause[p][p]/length;
}
realStack.add(oneClause);
}
}
public String getI(int size){
String temp = "";
for(int i = 0; i < numvariable-size; i++){
temp = temp+"I";
}
return temp;
}
public double[][] makeSig (String path){
char next;
double a0 = 0;
double a1 = 0;
double a2 = 0;
double a3 = 0;
double[][]ul,ur,ll,lr;
double [][] orig = new double[2][2];
if(path.charAt(path.length()-1)=='I'){
orig[0][0] = 1;
orig[0][1] = 0;
orig[1][0] = 0;
orig[1][1] = 1;
}else {
if(path.charAt(path.length()-1)=='0'){
orig[0][0] = 1;
orig[0][1] = 0;
orig[1][0] = 0;
orig[1][1] = 0;
}else if(path.charAt(path.length()-1)=='1'){
orig[0][0] = 0;
orig[0][1] = 0;
orig[1][0] = 0;
orig[1][1] = 1;
}
}
for(int i = path.length()-2; i>=0; i--){
next = path.charAt(i);
if(next=='I'){
a0 = 1;
a1 = 0;
a2 = 0;
a3 = 1;
}else {
if(next=='0'){
a0 = 1;
a1 = 0;
a2 = 0;
a3 = 0;
}else if(next=='1'){
a0 = 0;
a1 = 0;
a2 = 0;
a3 = 1;
}
}
ul = multiply(a0, clone(orig));
ur = multiply(a1, clone(orig));
ll = multiply(a2, clone(orig));
lr = multiply(a3, clone(orig));
orig = makeLarge(ul, ur, ll, lr);
}
return orig;
}
public double[][] multiply(double c, double[][] mat){
double [][] temp = new double[mat.length][mat.length];
for (int i = 0; i<mat.length; i++){
for (int j = 0; j<mat[0].length; j++){
temp[i][j] = c*mat[i][j];
}
}
return temp;
}
public double[][] makeLarge(double[][] ul, double[][] ur, double[][] ll, double[][]lr){
double [][] temp = new double[ul.length*2][ul.length*2];
for(int i = 0; i<ul.length; i++){
for(int j = 0; j<ul.length; j++){
temp[i][j] = ul[i][j];
}
}
for(int i = 0; i<ul.length; i++){
for(int j = 0; j<ul.length; j++){
temp[i][j+ul.length] = ur[i][j];
}
}
for(int i = 0; i<ul.length; i++){
for(int j = 0; j<ul.length; j++){
temp[i+ul.length][j] = ll[i][j];
}
}
for(int i = 0; i<ul.length; i++){
for(int j = 0; j<ul.length; j++){
temp[i+ul.length][j+ul.length] = lr[i][j];
}
}
return temp;
}
public double[][] clone(double[][] mat){
double [][]temp = new double[mat.length][mat.length];
for (int i = 0; i<mat.length; i++){
for(int j = 0; j<mat[0].length; j++){
temp[i][j] = mat[i][j];
}
}
return temp;
}
public double[][] makeProjector(int [] path, int ind) {
String str = "";
int zeroCount = 0;
int max = (int)pow(2,numvariable);
double [] row = new double[max];
double[][] matrix= new double[max][max];
int [] bits= new int [numvariable];
chain = new ArrayList<String>();
makePi();
for(int i=0; i<chain.size(); i++){
String temp1 = chain.get(i);
for(int j = 0; j<path.length; j++){
bits[path[numvariable-1-j]]=Integer.parseInt(""+temp1.charAt(j));
}
for(int j=bits.length-1; j>=0; j--){
str=str+""+bits[j];
}
zeroCount = Todecimal(str);
for(int j = 0; j<max; j++){
if(j==zeroCount){
row[j] = 1;
}else {
row[j] = 0;
}
}
for(int j = 0; j<max; j++){
matrix[i][j] = row[j];
}
str = "";
}
/*for(int i=0; i<chain.size(); i++){
String temp1 = chain.get(i);
for(int j = path.length-1; j>=0; j--){
str = str+temp1.charAt(numvariable-path[j]-1);
}
zeroCount = Todecimal(str);
for(int j = 0; j<max; j++){
if(j==zeroCount){
row[j] = 1;
}else {
row[j] = 0;
}
}
for(int j = 0; j<max; j++){
matrix[i][j] = row[j];
//if(i==1)
//System.out.println(i);
}
str = "";
}*/
return matrix;
}
public double[][] matMultiply(double[][]mat1, double[][] mat2){
double[][]prod = new double[mat1.length][mat1.length];
for(int i = 0; i<prod.length; i++){
for(int j = 0; j<prod.length; j++) {
prod[i][j] = 0;
}
}
for(int i = 0; i<prod.length; i++){
for(int j = 0; j<prod.length; j++) {
for(int k = 0; k<prod.length; k++){
prod[i][j] += mat1[i][k]*mat2[k][j];
}
}
}
return prod;
}
public int Todecimal (String binary){
int sum=0;
for (int i=binary.length()-1; i>=0; i--){
String bit = ""+binary.charAt(i);
int bitval = Integer.parseInt(bit);
int factor = (int)pow(2, binary.length()-1-i);
sum += bitval*factor;
}
return sum;
}
public String reverseString(String st){
String temp = "";
for(int i = st.length()-1; i>=0; i--){
temp = temp+st.charAt(i);
}
return temp;
}
public String Tobinary(int decimal, String path){
int remainder;
if(decimal<=1){
path = path+decimal;
return path;
}
remainder = decimal % 2;
path = path+remainder;
return Tobinary(decimal>>1, path);
}
public String addZero(String s, int l){
int b = l-s.length();
for(int i = 0; i<b; i++){
s = "0"+""+s;
}
return s;
}
}
|