/** * * de Bruijn sequences in JaCoP. * * This variant uses IterateSolutionListener (defined in the search method) * for generating a specific amount of solution. * * * This model is based on http://www.hakank.org/JaCoP/DeBruijn.java . * * This is a port from my MiniZinc model * http://www.hakank.org/minizinc/debruijn_binary.mzn * * and is explained somewhat in the swedish blog post * "Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc" * http://www.hakank.org/webblogg/archives/001209.html * * Related programs: * - "Normal" de Bruijn sequences * CGI program for calculating the sequences * http://www.hakank.org/comb/debruijn.cgi * http://www.hakank.org/comb/deBruijnApplet.html (as Java applet) * * * - "Arbitrary" de Bruijn sequences * Program "de Bruijn arbitrary sequences" * http://www.hakank.org/comb/debruijn_arb.cgi * * This (swedish) blog post explaines the program: * "de Bruijn-sekvenser av godtycklig längd" * http://www.hakank.org/webblogg/archives/001114.html * * * JaCoP Model by Hakan Kjellerstrand (hakank@bonetmail.com) * Also see http://www.hakank.org/JaCoP/ * */ import JaCoP.constraints.*; import JaCoP.core.*; import JaCoP.search.*; import java.io.*; import java.util.*; import java.text.*; public class DeBruijnIterate { // // Note: The names is the same as the MiniZinc model for // easy comparison. // // These parameters may be set by the user: // - base // - n // - m int base; // the base to use. Also known as k. int n; // number of bits representing the numbers int m; // length of the sequence, defaults to m = base^n // The constraint variables Store store; IntVar[] x; // the decimal numbers IntVar[][] binary; // the representation of numbers in x, in the choosen base IntVar[] bin_code; // the de Bruijn sequence (first number in binary) // // the model // public void model(int in_base, int in_n, int in_m) { store = new Store(); base = in_base; n = in_n; int pow_base_n = HakankUtil.pow(base,n); // base^n, the range of integers m = pow_base_n; if (in_m > 0) { if (in_m > m) { System.out.println("m must be <= base^n (" + m + ")"); System.exit(1); } m = in_m; } // decimal representation, ranges from 0..base^n-1 x = new IntVar[m]; for(int i = 0; i < m; i++) { x[i] = new IntVar(store, "x_" + i, 0, pow_base_n-1); } // // convert between decimal number in x[i] and "base-ary" numbers // in binary[i][0..n-1]. // // (This corresponds to the predicate toNum in the MiniZinc model) // // calculate the weights array int[] weights = new int[n]; int w = 1; for(int i = 0; i < n; i++) { weights[n-i-1] = w; w *= base; } // connect binary <-> x binary = new IntVar[m][n]; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { binary[i][j] = new IntVar(store, "binary_" + i + "_" + j, 0, base-1); } store.impose(new SumWeight (binary[i], weights, x[i])); } // // assert the the deBruijn property: element i in binary starts // with the end of element i-1 // for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { store.impose(new XeqY(binary[i-1][j], binary[i][j-1])); } } // ... "around the corner": last element is connected to the first for(int j = 1; j < n; j++) { store.impose(new XeqY(binary[m-1][j], binary[0][j-1])); } // // This is the de Bruijn sequence, i.e. // the first element of of each row in binary[i] // bin_code = new IntVar[m]; for(int i = 0; i < m; i++) { bin_code[i] = new IntVar(store, "bin_code_" + i, 0, base-1); store.impose(new XeqY(bin_code[i], binary[i][0])); } // All values in x should be different store.impose(new Alldifferent(x)); // Symmetry breaking: the minimum value in x should be the // first element. store.impose(new Min(x, x[0])); } // end model // // Search // public void search(int numGen) { SelectChoicePoint select = new SimpleSelect (bin_code, new SmallestDomain(), new IndomainMin () ); Search search = new DepthFirstSearch (); /* // 2008-08-20: // If we only need _one_ batch of numGen solutions, // SimpleSolutionListener.setSolutionLimit() may be used. SimpleSolutionListener simple = new SimpleSolutionListener(); search.setSolutionListener(simple); simple.setSolutionLimit(numGen); search.getSolutionListener().recordSolutions(true); search.setAssignSolution(false); boolean result = search.labeling(store, select); if (result) { search.printAllSolutions(); } */ /* * generate numGen solutions in batches of numGen, * but maximum 200000 batches. */ /* IterateSolutionListener listener = new IterateSolutionListener(); listener.hookUp(search); if (numGen > 1) { listener.solutionLimit = numGen; } */ search.getSolutionListener().recordSolutions(true); search.setAssignSolution(false); int i = 0; int totalSolutions = 0; boolean result = true; // max 200000 batches while (result && i < 200000) { result = search.labeling(store, select); System.out.println("\nIteration # " + i + " (" + result + ")"); if (result) { i++; search.printAllSolutions(); totalSolutions += search.getSolutionListener().solutionsNo(); } } System.out.println("Total # iterations " + i); System.out.println("Total # solutions " + totalSolutions); } // // Running the program // * java DeBruijn base n // * java DeBruijn base n m // public static void main(String args[]) { int base = 2; int n = 5; int m = 0; int numSolutions = 10; // how many solutions to generate if (args.length >= 1) { base = Integer.parseInt(args[0]); } if (args.length >= 2) { n = Integer.parseInt(args[1]); } if (args.length >= 3) { m = Integer.parseInt(args[2]); } if (args.length >= 4) { numSolutions = Integer.parseInt(args[3]); } System.out.println("Using base: " + base + " n: " + n + " m: " + m + " generating " + numSolutions + " solutions"); DeBruijnIterate debruijn = new DeBruijnIterate(); debruijn.model(base, n, m); debruijn.search(numSolutions); } // end main } // end class