SHOW:
|
|
- or go back to the newest paste.
| 1 | class Bt {
| |
| 2 | int[] unsorted={3,5,2,0,1,8,6,-1};
| |
| 3 | int[] candidate; | |
| 4 | int[] best; | |
| 5 | public static void main (String[] args) {
| |
| 6 | Bt b= new Bt(); | |
| 7 | b.bt(); | |
| 8 | b.print(b.best); | |
| 9 | } | |
| 10 | void bt() {
| |
| 11 | if (accept (candidate)) {
| |
| 12 | best= new int[candidate.length]; | |
| 13 | System.arraycopy (candidate, 0, best, 0, candidate.length); | |
| 14 | return; | |
| 15 | //System.exit (0); | |
| 16 | } | |
| 17 | if (reject (candidate)) return; | |
| 18 | if (!augment ()) return; | |
| 19 | do {
| |
| 20 | bt(); | |
| 21 | } while (next()); | |
| 22 | diminish (); | |
| 23 | } | |
| 24 | public boolean augment () {
| |
| 25 | if (candidate==null) {
| |
| 26 | candidate= new int[1]; | |
| 27 | candidate[0]=0; | |
| 28 | return true; | |
| 29 | } | |
| 30 | int i; | |
| 31 | boolean b[]= new boolean [unsorted.length]; | |
| 32 | // add the smallest index not present | |
| 33 | for (i=0;i<candidate.length;i++) | |
| 34 | b[candidate[i]]=true; | |
| 35 | // for (i=candidate[candidate.length-1];i<unsorted.length;i++) | |
| 36 | for (i=0;i<unsorted.length;i++) | |
| 37 | if (!b[i]) break; | |
| 38 | // add one element if possible. | |
| 39 | if(i<unsorted.length) {
| |
| 40 | int r[]= new int[candidate.length+1]; | |
| 41 | System.arraycopy (candidate, 0, r, 0, candidate.length); | |
| 42 | r[r.length-1]=i; | |
| 43 | candidate=r; | |
| 44 | return true; | |
| 45 | } | |
| 46 | return false; | |
| 47 | } | |
| 48 | public boolean next () {
| |
| 49 | if (candidate==null) {
| |
| 50 | System.out.println ("cannot be empty.");
| |
| 51 | System.exit (0); | |
| 52 | } | |
| 53 | int i; | |
| 54 | boolean b[]= new boolean [unsorted.length]; | |
| 55 | // add the smallest index not present | |
| 56 | for (i=0;i<candidate.length;i++) | |
| 57 | b[candidate[i]]=true; | |
| 58 | for (i=candidate[candidate.length-1];i<unsorted.length;i++) | |
| 59 | if (!b[i]) break; | |
| 60 | // substitute the last element if possible. | |
| 61 | if(i<unsorted.length) {
| |
| 62 | candidate[candidate.length-1]=i; | |
| 63 | return true; | |
| 64 | } | |
| 65 | return false; | |
| 66 | } | |
| 67 | public void diminish () {
| |
| 68 | if ((candidate!=null)&&(candidate.length>0)) {
| |
| 69 | int r[]= new int[candidate.length-1]; | |
| 70 | System.arraycopy (candidate, 0, r, 0, candidate.length-1); | |
| 71 | candidate=r; | |
| 72 | } | |
| 73 | } | |
| 74 | public boolean accept (int[] candidate) {
| |
| 75 | if (candidate==null) return false; | |
| 76 | if (!reject(candidate) && candidate.length==unsorted.length) return true; | |
| 77 | return false; | |
| 78 | } | |
| 79 | public boolean reject (int[] candidate) {
| |
| 80 | if ((candidate==null)||(candidate.length<2)) return false; | |
| 81 | int i; | |
| 82 | for (i=1;i<candidate.length;i++) | |
| 83 | if (unsorted[candidate[i-1]]>unsorted[candidate[i]]) return true; | |
| 84 | return false; | |
| 85 | } | |
| 86 | public void print (int[] a) {
| |
| 87 | if (a==null) {
| |
| 88 | System.out.println ("Empty");
| |
| 89 | return; | |
| 90 | } | |
| 91 | for (int i=0;i<a.length;i++) | |
| 92 | System.out.print (a[i] + " "); | |
| 93 | System.out.println(); | |
| 94 | } | |
| 95 | } |
