Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Bt {
- int[] unsorted={3,5,2,0,1,8,6,-1};
- int[] candidate;
- int[] best;
- public static void main (String[] args) {
- Bt b= new Bt();
- b.bt();
- b.print(b.best);
- }
- void bt() {
- if (accept (candidate)) {
- best= new int[candidate.length];
- System.arraycopy (candidate, 0, best, 0, candidate.length);
- return;
- //System.exit (0);
- }
- if (reject (candidate)) return;
- if (!augment ()) return;
- do {
- bt();
- } while (next());
- diminish ();
- }
- public boolean augment () {
- if (candidate==null) {
- candidate= new int[1];
- candidate[0]=0;
- return true;
- }
- int i;
- boolean b[]= new boolean [unsorted.length];
- // add the smallest index not present
- for (i=0;i<candidate.length;i++)
- b[candidate[i]]=true;
- // for (i=candidate[candidate.length-1];i<unsorted.length;i++)
- for (i=0;i<unsorted.length;i++)
- if (!b[i]) break;
- // add one element if possible.
- if(i<unsorted.length) {
- int r[]= new int[candidate.length+1];
- System.arraycopy (candidate, 0, r, 0, candidate.length);
- r[r.length-1]=i;
- candidate=r;
- return true;
- }
- return false;
- }
- public boolean next () {
- if (candidate==null) {
- System.out.println ("cannot be empty.");
- System.exit (0);
- }
- int i;
- boolean b[]= new boolean [unsorted.length];
- // add the smallest index not present
- for (i=0;i<candidate.length;i++)
- b[candidate[i]]=true;
- for (i=candidate[candidate.length-1];i<unsorted.length;i++)
- if (!b[i]) break;
- // substitute the last element if possible.
- if(i<unsorted.length) {
- candidate[candidate.length-1]=i;
- return true;
- }
- return false;
- }
- public void diminish () {
- if ((candidate!=null)&&(candidate.length>0)) {
- int r[]= new int[candidate.length-1];
- System.arraycopy (candidate, 0, r, 0, candidate.length-1);
- candidate=r;
- }
- }
- public boolean accept (int[] candidate) {
- if (candidate==null) return false;
- if (!reject(candidate) && candidate.length==unsorted.length) return true;
- return false;
- }
- public boolean reject (int[] candidate) {
- if ((candidate==null)||(candidate.length<2)) return false;
- int i;
- for (i=1;i<candidate.length;i++)
- if (unsorted[candidate[i-1]]>unsorted[candidate[i]]) return true;
- return false;
- }
- public void print (int[] a) {
- if (a==null) {
- System.out.println ("Empty");
- return;
- }
- for (int i=0;i<a.length;i++)
- System.out.print (a[i] + " ");
- System.out.println();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement