I would like to solve a problem of getting all the possible combinations for several people to cross a path, so that two nodes can not be visited by several people.
The ideal case would be to store the elements in a list but when using recursion the elements of the list at the end would be null.
The fact is that I have made an algorithm that prints all the solutions and prints them well the case is that I want to save them in a file, then instead of printing them I write them in a file.
The fact is that when I read the elements that I had introduced as [1,2,3], [2,1,3], [1,3,2], [2,3,1], [ 3,1,2] and [3,2,1] are all read as [1,2,3], [1,2,3], [1,2,3], [1,2,3], [1,2,3] and [1,2,3].
Does anyone know why this happens?
Code:
package elements;
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Combine{
public static final int nNodes = 3;
public static final int nVehicles = 3;
private ObjectOutputStream output= new ObjectOutputStream( new FileOutputStream("Solutions.bin"));
// nodes
private Node[] nodes;
private int nUnvisitedNodes = nNodes;
private List<Node[][]> list = new ArrayList<>();
// solution
private Node[][] sol = new Node[nVehicles][];
// no of solutions already found and printed
int nSolutions = 0;
public Combine() throws IOException {
// init nodes
nodes = new Node[nNodes];
for (int nix = 0; nix < nodes.length; nix++) {
nodes[nix] = new Node(nix + 1); // node names are 1-based
}
// search for solutions -- person 0 first
tryVehicle0();
try {
ObjectOutputStream output= new ObjectOutputStream( new FileOutputStream("numberSols.txt"));
output.writeInt(nSolutions);
output.close();
} catch (IOException e) {
e.printStackTrace();
}
output.close();
readSolution();
this.print();
}
private void tryVehicle0() {
if (nUnvisitedNodes == 0) { // done
storeSolution();
} else {
// assuming this is not the last person, this person may visit 1 through nUnvisitedNodes nodes
// (in a canonical solution person 0 cannot visit 0 nodes)
int maxVisits = nUnvisitedNodes;
for (int nNodesToVisit = 1; nNodesToVisit <= maxVisits; nNodesToVisit++) {
sol[0] = new Node[nNodesToVisit];
tryNode(0, sol[0], 0);
sol[0] = null;
}
}
}
private void tryVehicle(int person) {
assert person > 0;
if (nUnvisitedNodes == 0) { // solution complete
storeSolution();
} else {
if (person < nVehicles) { // still persons to try
if (person == nVehicles - 1) { // this is the last person
// person must visit all remaining nodes
// in a canonical solution, first node must be greater than first node visited by previous person
int nNodesToVisit = nUnvisitedNodes;
sol[person] = new Node[nNodesToVisit];
tryNodeWithMininum(person, sol[person], 0, sol[person - 1][0].name + 1);
sol[person] = null;
} else {
// since this is not the last person, this person may visit 1 through nUnvisitedNodes nodes
// in a canonical solution, first node must be greater than first node visited by previous person
int maxVisits = nUnvisitedNodes;
for (int nNodesToVisit = 1; nNodesToVisit <= maxVisits; nNodesToVisit++) {
sol[person] = new Node[nNodesToVisit];
tryNodeWithMininum(person, sol[person], 0, sol[person - 1][0].name + 1);
sol[person] = null;
}
}
}
}
}
private void tryNode(int person, Node[] personSol, int nix) {
if (nix == personSol.length) { // this person's solution complete
tryVehicle(person + 1);
} else {
for (Node candidateNode : nodes) {
if (this.visit(candidateNode)) {
personSol[nix] = candidateNode;
tryNode(person, personSol, nix + 1);
personSol[nix] = null;
this.unvisit(candidateNode);
}
}
}
}
private void tryNodeWithMininum(int person, Node[] personSol, int nix, int minNodeName) {
for (Node candidateNode : nodes) {
if (candidateNode.getName() >= minNodeName) {
if ( this.visit(candidateNode)) {
personSol[nix] = candidateNode;
tryNode(person, personSol, nix + 1);
personSol[nix] = null;
this.unvisit(candidateNode);
}
}
}
}
private void storeSolution() {
nSolutions++;
Node[][] sol2 = Arrays.copyOf(sol, sol.length);
try {
output.writeObject(sol);
} catch (IOException e) {
e.printStackTrace();
}
}
private void readSolution(){
try {
ObjectInputStream input=new ObjectInputStream(new FileInputStream("numberSols.txt"));
int numberSol = input.readInt();
input.close();
ObjectInputStream input2=new ObjectInputStream(new FileInputStream("Solutions.bin"));
for(int i=0; i < numberSol; i++){
Node[][] node = (Node[][]) input2.readObject();
this.list.add(node);
}
} catch (IOException | ClassNotFoundException e) {
e.printStackTrace();
}
}
private void print(){
int i=1;
for(Node[][] node: this.list){
System.out.println("Sol "+i);
for (int pix = 0; pix < nVehicles; pix++) {
System.out.println(" Vehicle " + pix + " = " + Arrays.toString(node[pix]));
}
i++;
}
}
public static void main(String[] args) {
try {
new Combine();
} catch (IOException e) {
e.printStackTrace();
}
}
/** visits node if not already visited */
public boolean visit(Node node) {
if (node.visited) {
return false;
} else {
node.visited = true;
nUnvisitedNodes--;
return true;
}
}
/** undoes visit (that is, backtracks) */
public void unvisit(Node node) {
assert node.visited : node.getName();
nUnvisitedNodes++;
node.visited = false;
}
}