|
This version finally works perfectly. Even the freezing point appears to work quite well. I wrote this version by adaptation from version 2. This version is a twin version to Version 4; the two versions are supposed to generate the same data, which is for the most part true, except for a little randomness that causes data instability. Version 4 runs slower than Version 5.
import java.io.*;
import static java.lang.Math.*;
import java.util.*;
public class QSATsolver5 {
private int clausesize = 3;
private int numvariable = 7;
private int numclause = 5;
private int numinstances = 50;
private ArrayList<String> stack = new ArrayList<String>(); //nonnullspace list
private ArrayList<String> chain = new ArrayList<String>();
private int success= 0;
private ArrayList<Integer> temp2var = new ArrayList <Integer> ();
private ArrayList<ArrayList <Integer>> temp5var = new ArrayList <ArrayList<Integer>> ();
private ArrayList <State> completeState = new ArrayList <State>();
private ArrayList<ArrayList <State>> completeStateStack = new ArrayList<ArrayList <State>>();
private ArrayList<Integer> left = new ArrayList<Integer>();
private ArrayList<Integer> right = new ArrayList<Integer>();
private ArrayList <State> sumStack = new ArrayList<State>();
private ArrayList <State> solutionStack = new ArrayList<State>();
private ArrayList<State> oneNullState = new ArrayList<State>();
private ArrayList <ArrayList<State>> nullVectorStack = new ArrayList<ArrayList<State>>();
private ArrayList <ArrayList<State>> nullVectorStack2 = new ArrayList<ArrayList<State>>();
public static void main(String[] args) {
// TODO Auto-generated method stub
QSATsolver5 qs = new QSATsolver5();
qs.generate();
}
public void generate(){
ArrayList<Double>temp = new ArrayList<Double>();
ArrayList<ArrayList<Double>> temp2 = new ArrayList<ArrayList<Double>>();
ArrayList<ArrayList<ArrayList<Double>>> temp5 = new ArrayList<ArrayList<ArrayList<Double>>>();
double length = 0;
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;
for(int i = 0; i < clausesize; i++){
v = (int)(Math.random()*numvariable)+1;
while(taken[v-1]==true){
v = (int)(Math.random()*numvariable)+1;
}
taken[v-1] = true;
temp2var.add(new Integer(v));
}
for(int i = 0; i < taken.length; i++){
taken[i] = false;
}
int max5 = (int)pow(2,clausesize);
for (int i = 0; i < max5; i++){
int hasTerm =(int)(Math.random()*2);
if(hasTerm==1) {
double real = Math.random();
temp.add(new Double(real));
} else {
double real = 0;
temp.add(new Double(real));
}
temp2.add(temp);
temp = new ArrayList<Double>();
}
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;
}
}
if(length==0){
length=1;
}
//length = sqrt(length);
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 in these
temp5var.add(temp2var);
temp2var = new ArrayList <Integer> ();
length=0; //newly added
}
//find the |phi> of each clause temp5
generateState(temp5);
System.out.println(completeStateStack.size()); //delete?
int max = (int)pow(2,numvariable);
double realsum=0;
double imaginarysum=0;
String label="";
for (int t = 0; t < max; t++){
for (int z = 0; z < completeStateStack.size(); z++){
ArrayList <State> cs = completeStateStack.get(z);
realsum += cs.get(t).probab;
label = cs.get(t).label;
}
State tempstate = new State(label,realsum,Todecimal(label));
realsum = 0;
sumStack.add(tempstate);
}
//System.out.println("sStack:"+sumStack.size());
if(varifySolution()){
success++;
}
temp5var = new ArrayList <ArrayList<Integer>> ();
temp5 = new ArrayList<ArrayList<ArrayList<Double>>>();
chain = new ArrayList<String>();
completeStateStack = new ArrayList<ArrayList <State>>();
//nullVectorStack2= new ArrayList<ArrayList<State>>();
//nullVectorStack= new ArrayList<ArrayList<State>>();
sumStack = new ArrayList<State>();
solutionStack = new ArrayList<State>();
stack = new ArrayList<String>();
}
System.out.println(success);
}
public boolean varifySolution(){
for (int i = 0; i<sumStack.size(); i++){
State st = sumStack.get(i);
if(st.probab==0){
solutionStack.add(st);
}
}
for (int i = 0; i<sumStack.size(); i++){
State st = sumStack.get(i);
if(st.probab==0){
return true;
}
}
return false;
}
public void generateState(ArrayList<ArrayList<ArrayList<Double>>> temp5){
int [] varnumber = new int [clausesize];
String myleft, myright;
ArrayList <State> temp2again = new ArrayList <State>();
ArrayList<ArrayList <State>> temp5again = new ArrayList <ArrayList <State>>();
int max = (int)pow(2,numvariable-clausesize);
for(int j = 0; j<max; j++) {
String temp3 = Tobinary(j,"");
temp3 = reverseString(temp3);
if (temp3.length()<(numvariable-clausesize)) {
temp3 = addZero(temp3, (numvariable-clausesize));
}
if((numvariable-clausesize)>0) {
chain.add(temp3);
}
}
int max2 = (int) pow(2,clausesize);
//clause are int temp5
//temp2again is the clause with coefficient and string linked together
for (int g = 0; g < temp5.size(); g++) { //temp5 has 15 elements
ArrayList<ArrayList<Double>> clause = temp5.get(g); //the 8 element clause
for(int m = 0; m < clause.size(); m++) {
ArrayList<Double> list = clause.get(m); //the 2 element complex number
String temp3 = Tobinary(m,"");
temp3 = reverseString(temp3);
if (temp3.length() < clausesize) {
temp3 = addZero(temp3, clausesize);
}
double x1 = Double.parseDouble(""+list.get(0));
temp2again.add(new State(temp3, x1));
}
temp5again.add(temp2again);
temp2again = new ArrayList <State>();
}
for (int g = 0; g<temp5var.size(); g++){
//temp5var has 15 elements.
ArrayList<Integer> list1 = temp5var.get(g); //list1 is a temp2var:3 int list
for(int i = 0; i<list1.size(); i++) {
varnumber[i] = Integer.parseInt(""+list1.get(i))-1;
System.out.print(varnumber[i]+" "); //prints
//varnumber[i] value start at 0 not 1.
}
System.out.println("");//prints
String [] pattern = new String [clausesize];
int [] pattern2 = new int[clausesize];
ArrayList <State> list2 = temp5again.get(g); //list2 has 8 elements
for(int h=0; h<list2.size(); h++){
State st = list2.get(h); //st is a State
double one = st.probab/max;
String pat = st.label;
for (int s = 0; s < clausesize; s++) {
pattern[s] = ""+pat.charAt(clausesize-1-s);
pattern2[s] = Integer.parseInt(pattern[s]);
}
int [] varnumber2 = getCopy(varnumber);
sort(varnumber2, pattern2);
for(int l = 0; l < chain.size(); l++){
String str = chain.get(l);
for (int k = 0; k < varnumber2.length; k++){
String insertion = ""+pattern2[k];
if(varnumber2[k] == 0){
myleft=str;
myright="";
}
else if(varnumber2[k] == numvariable-1){
myright=str;
myleft="";
}
else {
myright = str.substring(str.length()-varnumber2[k]);
myleft = str.substring(0, str.length()-varnumber2[k]);
}
str = ""+myleft+insertion+myright;
}
State ast = new State(str, one, Todecimal(str));
completeState.add(ast);
}
if(chain.size()==0) {
State ast = new State(pat, one, Todecimal(pat));
completeState.add(ast);
}
} //completeState has 2^7 component states
//now we are going to put the 128 pure states in order
String [] a1 = new String [completeState.size()];
double [] a2 = new double [completeState.size()];
int [] a4 = new int [completeState.size()];
int totalstates = (int) pow (2,numvariable);
for(int w = 0; w<completeState.size(); w++){
State onest = completeState.get(w);
a1[w] = onest.label;
a2[w] = onest.probab;
a4[w] = onest.index;
}
sort2(a1, a2, a4); //starting with 0000000 end with 1111111
completeState = new ArrayList <State>();
for (int c = 0; c < totalstates; c++) {
State tempstate = new State(a1[c], a2[c], a4[c]);
completeState.add(tempstate);
}
double length=0;
for(int u=0; u<completeState.size(); u++){
State st4= completeState.get(u);
length+=st4.probab;
}
if(length==0){
length=1;
}
for(int u=0; u<completeState.size(); u++){
State st4= completeState.get(u);
st4.probab/=length;
}
completeStateStack.add(completeState);
completeState = new ArrayList <State>();
//just inside temp5var iter.
}
}
public int [] getCopy(int [] varnumber){
int[] oldvarnumber = new int [varnumber.length];
for(int i = 0; i<varnumber.length; i++) {
oldvarnumber[i] = varnumber[i];
}
return oldvarnumber;
}
public void sort(int [] a, int [] b){
int temp = 0;
int temp2;
int temp3;
for(int i = 0; i < a.length-1; i++){
temp = i;
for(int j = i+1; j < a.length; j++){
if(a[j] < a[temp]){
temp = j;
}
}
temp2 = a[temp];
a[temp] = a[i];
a[i] = temp2;
temp3 = b[temp];
b[temp] = b[i];
b[i] = temp3;
}
}
public void sort2(String[] str, double [] a, int []strval ){
int temp = 0;
int temp2;
double temp3;
double temp4;
String temp5;
for(int i = 0; i<strval.length-1; i++){
temp = i;
for(int j = i+1; j<strval.length; j++){
if(strval[j]<strval[temp]){
temp = j;
}
}
temp2 = strval[temp];
strval[temp] = strval[i];
strval[i] = temp2;
temp4 = a[temp];
a[temp] = a[i];
a[i] = temp4;
temp5 = str[temp];
str[temp] = str[i];
str[i] = temp5;
}
}
public String addZero(String s, int l){
int b = l-s.length();
for(int i = 0; i<b; i++){
s = "0"+""+s;
}
return s;
}
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 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;
}
private class State {
String label;
double probab;
int index;
public State(String str, double a){
label = str;
probab = a;
}
public State( double a){
probab = a;
}
public State(String str, double a, int ind){
label = str;
probab = a;
index = ind;
}
}
}
|