Advertisement
Guest User

Stupid way to find combination

a guest
Mar 29th, 2017
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.09 KB | None | 0 0
  1. /**
  2.  * This class requires jgrapht library - http://jgrapht.org/
  3.  */
  4. public class Main {
  5.  
  6.     static DirectedGraph<Vertex, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);
  7.  
  8.     public static void main(String[] args) {
  9.         byte[] sourceArr = {1, 2, 3, 4, 5, 6, 7, 8};
  10.         Vertex source = new Vertex(sourceArr);
  11.         Vertex dest = new Vertex(new byte[]{8, 7, 6, 5, 4, 3, 2, 1});
  12.  
  13.         List<Vertex> allVertexes = new ArrayList<>(factorial(sourceArr.length));
  14.         Instant start = Instant.now();
  15.         permute(sourceArr, arg -> {
  16.             Vertex v = new Vertex(arg);
  17.             graph.addVertex(v);
  18.             allVertexes.add(v);
  19.         });
  20.         for (ListIterator<Vertex> it = allVertexes.listIterator(); it.hasNext(); ) {
  21.  
  22.             Vertex curr = it.next();
  23.             List<Vertex> otherVertices = allVertexes.subList(it.nextIndex(), allVertexes.size());
  24.             otherVertices.iterator().forEachRemaining(arg -> {
  25.                 if (related(curr, arg)) {
  26.                     graph.addEdge(curr, arg);
  27.                 }
  28.             });
  29.         }
  30.  
  31.         GraphPath<Vertex, DefaultEdge> pathBetween = DijkstraShortestPath.findPathBetween(graph, source, dest);
  32.         System.out.println("Path length: " + (pathBetween.getEdgeList().size()));
  33.         System.out.println("Path: " + pathBetween.getVertexList());
  34.         System.out.println("Total edges: " + graph.edgeSet().size());
  35.         System.out.println("Total vertices: " + graph.vertexSet().size());
  36.  
  37.         System.out.println("duration -> " + Duration.between(start, Instant.now()).toMillis() / 1000.0 + " seconds");
  38.     }
  39.  
  40.     public static boolean related(Vertex curr, Vertex next) {
  41.         byte[] currValues = Arrays.copyOf(curr.getValues(), curr.getValues().length);
  42.         byte[] nextValues = Arrays.copyOf(next.getValues(), next.getValues().length);
  43.  
  44.         boolean first = false;
  45.         for (int idx = 0; idx < currValues.length; idx++) {
  46.  
  47.             if (currValues[idx] != nextValues[idx] && !first) {
  48.                 first = true;
  49.                 int size = 0;
  50.                 int pos = idx;
  51.                 // get the size of the permutated block
  52.                 while (nextValues[idx + ++size] != currValues[idx]) ;
  53.                 // get start of this block in source array
  54.                 while (currValues[++pos] != nextValues[idx]) ;
  55.                 // try to make arrays same and continue comparation
  56.                 for (int i = 0; i < size; i++) {
  57.                     if (idx + i < currValues.length && pos + i < currValues.length) {
  58.                         swap(currValues, idx + i, pos + i);
  59.                     } else return false;
  60.                 }
  61.                 continue;
  62.             }
  63.             // if we fail second time, there is no edge
  64.             if (currValues[idx] != nextValues[idx] && first) {
  65.                 return false;
  66.             }
  67.         }
  68.         return true;
  69.     }
  70.  
  71.     private static int factorial(int n) {
  72.         int result = 1;
  73.         for (int counter = 1; counter <= n; counter++) {
  74.             result *= counter;
  75.         }
  76.         return result;
  77.     }
  78.  
  79.  
  80.     /**
  81.      * From stackoverflow with small changes
  82.      */
  83.     // swap 2 elements of an array,
  84.     private static void swap(byte[] arr, int x, int y) {
  85.         byte temp = arr[x];
  86.         arr[x] = arr[y];
  87.         arr[y] = temp;
  88.     }
  89.  
  90.     private static void permute(byte[] arr, Consumer<byte[]> action) {
  91.         permute(arr, 0, arr.length - 1, action);
  92.     }
  93.  
  94.     private static void permute(byte[] arr, int i, int n, Consumer<byte[]> action) {
  95.         int j;
  96.         if (i == n) {
  97.             action.accept(arr);
  98.         } else {
  99.             for (j = i; j <= n; j++) {
  100.                 swap(arr, i, j);
  101.                 permute(arr, i + 1, n, action);
  102.                 swap(arr, i, j); // backtrack
  103.             }
  104.         }
  105.     }
  106. }
  107.  
  108. class Vertex {
  109.     private final byte[] values;
  110.  
  111.     public Vertex(byte[] sourceArr) {
  112.         this.values = Arrays.copyOf(sourceArr, sourceArr.length);
  113.     }
  114. //   generated hashCode, equals, toString and getter omitted
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement