SHARE
TWEET

backtracking

DulcetAirman Feb 6th, 2018 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ch.fhnw.claudemartin;
  2.  
  3. import java.util.Arrays;
  4. import java.util.Random;
  5. import java.util.Set;
  6. import java.util.TreeSet;
  7.  
  8. import javax.script.ScriptException;
  9.  
  10. public class SomeClass {
  11.  
  12.   final static class BinStr implements Comparable<BinStr> {
  13.     final private boolean[] data;
  14.  
  15.     public BinStr(final int n) {
  16.       this.data = new boolean[n];
  17.     }
  18.  
  19.     public BinStr(final boolean... data) {
  20.       this.data = Arrays.copyOf(data, data.length);
  21.     }
  22.  
  23.     char getChar(final int i) {
  24.       return this.data[i] ? '1' : '0';
  25.     }
  26.  
  27.     boolean get(final int i) {
  28.       return this.data[i];
  29.     }
  30.  
  31.     void set(final int i, final boolean value) {
  32.       this.data[i] = value;
  33.     }
  34.  
  35.     int getN() {
  36.       return this.data.length;
  37.     }
  38.  
  39.     @Override
  40.     public String toString() {
  41.       final StringBuffer s = new StringBuffer(this.data.length);
  42.       for (int i = 0; i < this.data.length; i++) {
  43.         s.append(this.getChar(i));
  44.         if (i > 1 && i % 100 == 0)
  45.           s.append("\n\t");
  46.       }
  47.       return s.toString();
  48.     }
  49.  
  50.     @Override
  51.     public int compareTo(final BinStr o) {
  52.       if (this.data.length != o.data.length)
  53.         return this.data.length - o.data.length;
  54.  
  55.       for (int i = 0; i < this.data.length; i++) {
  56.         if (this.data[i] != o.data[i])
  57.           return this.data[i] ? 1 : -1;
  58.       }
  59.       return 0;
  60.     }
  61.   }
  62.  
  63.   public static void main(final String[] args) throws ScriptException {
  64.     final TreeSet<BinStr> input = new TreeSet<>();
  65.     final int N = 20;
  66.     final boolean[] data = new boolean[N];
  67.     input.add(new BinStr(data));// all 0
  68.  
  69.     final Random r = new Random();
  70.     while (input.size() < N) {
  71.       for (int i = 0; i < data.length; i += r.nextInt(5)) {
  72.         data[i] = r.nextBoolean();
  73.       }
  74.       input.add(new BinStr(data));
  75.     }
  76.  
  77.     System.out.println("input is ready...");
  78.     if (N <= 20)
  79.       System.out.println(input);
  80.     // Find multiple strings by adding each result and staring over:
  81.     for (int i = 0; i < N; i++) {
  82.       final BinStr str = new BinStr(N);
  83.       final boolean found = find(0, str, input);
  84.       if (!found) {
  85.         System.out.println("not found");
  86.       } else {
  87.         System.out.println(str.toString());
  88.         input.add(str);
  89.       }
  90.       System.out.flush();
  91.     }
  92.   }
  93.  
  94.   public static boolean find(final int i, final BinStr str,
  95.       final Set<BinStr> input) {
  96.  
  97.     if (i == str.getN())
  98.       return !input.contains(str);
  99.  
  100.     str.set(i, false);
  101.     if (find(i + 1, str, input))
  102.       return true;
  103.  
  104.     str.set(i, true);
  105.     if (find(i + 1, str, input))
  106.       return true;
  107.  
  108.     return false;
  109.   }
  110.  
  111. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top