I'm working on a project where I need to use recursion, and arraylists/vectors to solve a 3-satisfiability instance. The task is to select a sub-set of integers, such that each set denoted below contains one or more elements of the sub-set. The constraint being that a number, i & its opposite, -i, cannot both be in the sub-set.
Vector<Vector<Integer>> matrix = new Vector<Vector<Integer>>();
for(int i=0;i<4;i++)
{
matrix.add(new Vector<Integer>());
}
the 2-dimensional vector/arraylist is then filled with numbers, for example:
1, -2, 3
-1, 2, 4
2, -3, 4
-1, -2, -3
if(startRec(matrix)
{
//solution is found
}
else
{
//no solution is possible
}
private boolean startRec(Vector<Vector<Integer>> matrix)
{ // I'm using trial and error to find a solution to the above problem. So in the below, matrix.get(0).get(i) is selected as part of a possibly correct set.
boolean success=false;
if(stagen(matrix.get(0).get(0), matrix))
{
success=true;
}
else if(stagen(matrix.get(0).get(1),matrix))
{
success=true;
}
else if(stagen(matrix.get(0).get(2),matrix))
{
success=true;
}
return success;
}
private boolean stagen(int input, Vector<Vector<Integer>> matrix)
{
removei(input, matrix) // this removes all Vector<Integer> that contain i. Those sets are considered satisfied, and no longer need to be addressed.
removenegative(input,matrix) // this removes all integers that are -input. Since i and -i cannot both be selected, I'm removing the -input.
//So if a set contained three ints, one of which was -input, it now contains 2.
boolean success=false;
if(stagen(matrix.get(0).get(0), matrix)) // since the original matrix.get(0) contained input, it was removed in removei(input,matrix), thus this is a one below the one called previously.
{
success=true;
}
else if(stagen(matrix.get(0).get(1),matrix))
{
success=true;
}
else if(stagen(matrix.get(0).get(2),matrix))
{
success=true;
}
return success;
}
I've removed the out of range checks, to make it more readable. But the process I'm confident is going on is this:
1, -2, 3 //1 is selected in the second line of startRec
-1, 2, 4
2, -3, 4
-1, -2, -3
//1, -2, 3 line is removed from consideration by method removei() as 1 has been selected
2, 4 // -1 has been removed as both 1,-1 cannot be selected.
2, -3, 4
-2, -3 // -1 removed.
2, 4 now 2 is the first number, so 2 is selected.
-2, 3, 4
-2, -3
//2, 4 removed via removei method.
3, 4 //-2 is removed, because 2 has been selected.
-3 //-2removed.
3, 4 //Now 3 is selected.
-3
//3, 4 line removed as it has been satisfied.
_____ //There's now an empty set here as -3 was deleted
//false is returned by stagen.
The program returns to the stagen which selected 3, and it now ideally now select 4 as the next letter. But I deleted that whole row.
Is there a way to do this without creating an unknown number of vectors?
2ndly, is there a significant difference between arraylists & vectors? I've been using arraylists, exclusively, but the project suggests vectors.
