Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * This class requires jgrapht library - http://jgrapht.org/
- */
- public class Main {
- static DirectedGraph<Vertex, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);
- public static void main(String[] args) {
- byte[] sourceArr = {1, 2, 3, 4, 5, 6, 7, 8};
- Vertex source = new Vertex(sourceArr);
- Vertex dest = new Vertex(new byte[]{8, 7, 6, 5, 4, 3, 2, 1});
- List<Vertex> allVertexes = new ArrayList<>(factorial(sourceArr.length));
- Instant start = Instant.now();
- permute(sourceArr, arg -> {
- Vertex v = new Vertex(arg);
- graph.addVertex(v);
- allVertexes.add(v);
- });
- for (ListIterator<Vertex> it = allVertexes.listIterator(); it.hasNext(); ) {
- Vertex curr = it.next();
- List<Vertex> otherVertices = allVertexes.subList(it.nextIndex(), allVertexes.size());
- otherVertices.iterator().forEachRemaining(arg -> {
- if (related(curr, arg)) {
- graph.addEdge(curr, arg);
- }
- });
- }
- GraphPath<Vertex, DefaultEdge> pathBetween = DijkstraShortestPath.findPathBetween(graph, source, dest);
- System.out.println("Path length: " + (pathBetween.getEdgeList().size()));
- System.out.println("Path: " + pathBetween.getVertexList());
- System.out.println("Total edges: " + graph.edgeSet().size());
- System.out.println("Total vertices: " + graph.vertexSet().size());
- System.out.println("duration -> " + Duration.between(start, Instant.now()).toMillis() / 1000.0 + " seconds");
- }
- public static boolean related(Vertex curr, Vertex next) {
- byte[] currValues = Arrays.copyOf(curr.getValues(), curr.getValues().length);
- byte[] nextValues = Arrays.copyOf(next.getValues(), next.getValues().length);
- boolean first = false;
- for (int idx = 0; idx < currValues.length; idx++) {
- if (currValues[idx] != nextValues[idx] && !first) {
- first = true;
- int size = 0;
- int pos = idx;
- // get the size of the permutated block
- while (nextValues[idx + ++size] != currValues[idx]) ;
- // get start of this block in source array
- while (currValues[++pos] != nextValues[idx]) ;
- // try to make arrays same and continue comparation
- for (int i = 0; i < size; i++) {
- if (idx + i < currValues.length && pos + i < currValues.length) {
- swap(currValues, idx + i, pos + i);
- } else return false;
- }
- continue;
- }
- // if we fail second time, there is no edge
- if (currValues[idx] != nextValues[idx] && first) {
- return false;
- }
- }
- return true;
- }
- private static int factorial(int n) {
- int result = 1;
- for (int counter = 1; counter <= n; counter++) {
- result *= counter;
- }
- return result;
- }
- /**
- * From stackoverflow with small changes
- */
- // swap 2 elements of an array,
- private static void swap(byte[] arr, int x, int y) {
- byte temp = arr[x];
- arr[x] = arr[y];
- arr[y] = temp;
- }
- private static void permute(byte[] arr, Consumer<byte[]> action) {
- permute(arr, 0, arr.length - 1, action);
- }
- private static void permute(byte[] arr, int i, int n, Consumer<byte[]> action) {
- int j;
- if (i == n) {
- action.accept(arr);
- } else {
- for (j = i; j <= n; j++) {
- swap(arr, i, j);
- permute(arr, i + 1, n, action);
- swap(arr, i, j); // backtrack
- }
- }
- }
- }
- class Vertex {
- private final byte[] values;
- public Vertex(byte[] sourceArr) {
- this.values = Arrays.copyOf(sourceArr, sourceArr.length);
- }
- // generated hashCode, equals, toString and getter omitted
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement