ArrayLists, References & Recursion

Question

Ich arbeite an einem Projekt, wo ich Rekursion und Arraylists/Vektoren verwenden muss, um eine 3-Erfüllbarkeit-Instanz zu lösen. Die Aufgabe besteht darin, eine Teilmenge von ganzen Zahlen auszuwählen, so dass jede der unten angegebenen Mengen ein oder mehrere Elemente der Teilmenge enthält. Die Einschränkung ist, dass eine Zahl, i & ihr Gegenteil, -i, nicht beide in der Untergruppe sein kann.

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; 
} 

Ich habe die aus Bereichsprüfungen entfernt, es besser lesbar zu machen:

Vector<Vector<Integer>> matrix = new Vector<Vector<Integer>>(); 
for(int i=0;i<4;i++) 
{ 
    matrix.add(new Vector<Integer>()); 
} 

die 2-dimensionale Vektor/Arraylist wird dann mit Zahlen, beispielsweise gefüllt. Aber der Prozess bin ich zuversichtlich, vor sich geht, ist dies:

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. 

Das Programm kehrt zum Stagen die 3 ausgewählt, und jetzt ist es nun idealerweise wählen 4 als den nächsten Buchstaben. Aber ich habe diese ganze Zeile gelöscht.

Gibt es eine Möglichkeit, dies zu tun, ohne eine unbekannte Anzahl von Vektoren zu erstellen?

Zweitens, gibt es einen signifikanten Unterschied zwischen Arraylists & Vektoren? Ich habe ausschließlich Arraylisten benutzt, aber das Projekt schlägt Vektoren vor.

Answer 1

Der erste Teil Ihrer Frage ist inkohärent. Ich werde jedoch näher auf die Unterschiede zwischen Vector und Arraylist:

• Wenn mehrere Threads eine Arraylist gleichzeitig zuzugreifen, dann müssen Sie extern an den Codeblock synchronisieren, die die Liste ändert.
• Intern verwenden beide ein Array, um die Datenstruktur zu pflegen. Wenn der Speicherplatz knapp wird, erhöht ArrayList seine Größe um 50%, während Vector seine Größe verdoppelt.

Siehe this Thread für eine detaillierte Erklärung.