Notes

public class TimeMatr {

private final Integer size;
private final ArrayList<ArrayList<Integer>> matrix = new ArrayList<>();

public TimeMatr(Integer size) {
this.size = size;
}

public void initialize() {
long startTime = System.nanoTime();
SecureRandom random = new SecureRandom();
for (int i = 0; i < size; i++) {
matrix.add(new ArrayList<>());
List<Integer> row = matrix.get(i);
for (int j = 0; j < size; j++) {
if (i != j) {
row.add(random.nextInt(14) + 1);

} else {
row.add(0);
}
}
}
long endTime = System.nanoTime();
System.out.printf("Initialization takes %.3f millisecondsn", (endTime - startTime) / 1000000.0);
}

public void outputMatrix() {
long startTime = System.nanoTime();
StringBuilder format = new StringBuilder();
format.append('[');
for (int i = 0; i < size; i++) {
format.append(" %3d");
}
format.append(']').append('n');
matrix.stream()
.forEach((row) -> {
System.out.printf(format.toString(), row.toArray());
});
long endTime = System.nanoTime();
System.out.printf("Output matrix takes %.3f millisecondsn", (endTime - startTime) / 1000000.0);
}

public Object[] fullSearch() {
long startTime = System.nanoTime();
List<Integer> minResult = null;
Long minTime = -1L;
for (int i = 0; i < size; i++) {
Object[] results = searchInDepth(new ArrayList<>(Arrays.asList(i)), 0);
if (results != null && (long) results[0] != -1 && results[1] != null) {
long time = (long) results[0];
if (time < minTime || minTime == -1) {
minTime = time;
minResult = new ArrayList<>((List) results[1]);
}
}
}
long endTime = System.nanoTime();
System.out.printf("Full search takes %.3f millisecondsn", (endTime - startTime) / 1000000.0);
return new Object[]{minTime, minResult};
}

public Object[] fullSearchWithParallelStream() {
long startTime = System.nanoTime();
Optional<Object[]> findFirst = IntStream.range(0, size)
.parallel()
.mapToObj(i -> {
return searchInDepthWithParallelStream(new ArrayList<>(Arrays.asList(i)), 0);
})
.filter(results -> results != null && (long) results[0] != -1 && results[1] != null && ((List) results[1]).size() == size)
.sorted((r1, r2) -> Long.compare((Long) r1[0], (Long) r2[0]))
.findFirst();
long endTime = System.nanoTime();
System.out.printf("Full search with parallel streams takes %.3f millisecondsn", (endTime - startTime) / 1000000.0);
return findFirst.get();
}

public Object[] fullSearchWithStream() {
long startTime = System.nanoTime();
Optional<Object[]> findFirst = IntStream.range(0, size)
.mapToObj(i -> {
return searchInDepthWithStream(new ArrayList<>(Arrays.asList(i)), 0);
})
.filter(results -> results != null && (long) results[0] != -1 && results[1] != null && ((List) results[1]).size() == size)
.sorted((r1, r2) -> Long.compare((Long) r1[0], (Long) r2[0]))
.findFirst();
long endTime = System.nanoTime();
System.out.printf("Full search with streams takes %.3f millisecondsn", (endTime - startTime) / 1000000.0);
return findFirst.get();
}

private Object[] searchInDepth(List<Integer> visited, long spentTime) {
if (visited.size() == size) {
return new Object[]{spentTime, new ArrayList<>(visited)};
}
List<Integer> minResult = null;
Long minTime = -1L;
int lastIndex = visited.get(visited.size() - 1);
ArrayList<Integer> row = matrix.get(lastIndex);
for (int j = 0; j < size; j++) {
if (!visited.contains(j)) {
spentTime += row.get(j);
List<Integer> newVisited = new ArrayList<>(visited);
newVisited.add(j);
Object[] results = searchInDepth(newVisited, new Long(spentTime));
if (results != null && (long) results[0] != -1 && results[1] != null) {
long time = (long) results[0];
if (time < minTime || minTime == -1) {
minTime = time;
minResult = new ArrayList<>((List) results[1]);
}
}
}
}
return new Object[]{minTime, new ArrayList<>(minResult)};
}

private Object[] searchInDepthWithStream(List<Integer> visited, final long spentTime) {
if (visited.size() == size) {
return new Object[]{spentTime, new ArrayList<>(visited)};
}
int lastIndex = visited.get(visited.size() - 1);
ArrayList<Integer> row = matrix.get(lastIndex);

Optional<Object[]> findFirst = IntStream.range(0, size)
.filter(i -> !visited.contains(i))
.mapToObj(i -> {
List<Integer> newVisited = new ArrayList<>(visited);
Long newTime = spentTime + row.get(i);
newVisited.add(i);
return searchInDepth(newVisited, newTime);
})
.filter(results -> results != null && (long) results[0] != -1 && results[1] != null)
.sorted((r1, r2) -> Long.compare((Long) r1[0], (Long) r2[0]))
.findFirst();
return findFirst.get();
}

private Object[] searchInDepthWithParallelStream(List<Integer> visited, long spentTime) {
if (visited.size() == size) {
return new Object[]{spentTime, new ArrayList<>(visited)};
}
int lastIndex = visited.get(visited.size() - 1);
ArrayList<Integer> row = matrix.get(lastIndex);

Optional<Object[]> findFirst = IntStream.range(0, size)
.parallel()
.filter(i -> !visited.contains(i))
.mapToObj(i -> {
List<Integer> newVisited = new ArrayList<>(visited);
Long newTime = spentTime + row.get(i);
newVisited.add(i);
return searchInDepth(newVisited, newTime);
})
.filter(results -> results != null && (long) results[0] != -1 && results[1] != null)
.sorted((r1, r2) -> Long.compare((Long) r1[0], (Long) r2[0]))
.findFirst();
return findFirst.get();
}
}