Silly Sort

对一个长度为N的整数序列，交换数据X和Y的代价是两数之和X+Y，通过两两交换数据使得该序列呈增序次序排列，求最小代价。

 

示例：{3 2 1}=4， {8 1 2 4}=17，{1 8 9 7 6}=41，{8 4 5 3 2 7}=34

 

 

前两个示例{3 2 1}和{8 1 2 4}，似乎给人贪心策略的感觉：每次选择代价最小的一对交换，使得至少一个数字能归位。但是后两个示例对贪心策略已经作了否定。一时也没有想到其他更好的方法，所以打算尝试搜索方法，即每次选择一个位置，将对应数交换到这个位置并标记，然后搜索继续往下进行，子搜索返回后再撤销交换并选定下一个位置，继续进行搜索尝试。实现搜索的过程中，发觉贪心策略得到的次优解，用来剪枝倒是挺不错。

 

但是经过测试发现，对示例{1 8 9 7 6}，搜索的方法得到的最小代价是42，仍然大于实际最优解41，所以应该还忽略了某些因素。于是继续探究示例中的奥妙，发现如果1和6先交换，虽然额外的引入了7个代价，但是后续的交换都是通过1来进行，反而使得最终结果更加优化，而且进确定，41的解也正是通过这种方法得到的。所以将实现分成了三步：1）贪心确定次优解，用来剪枝；2）简单搜索第一阶段求解；3）将最小数分别交换到其他位置后，再次进行简单搜索。

 

四个示例都是通过了，但是感觉搜索的效率总是比较让人担心，而且感觉自己的算法不是太正规的路数，好奇应该有某种正规的路数。的确，在网上搜到了比较正规的解法，而且还有一个酷酷的名字——置换群（http://hi.baidu.com/matrush/blog/item/2213e5d4267aa42107088bca.html ），里面的实现非常简洁巧妙，开阔了思路，受益良多。尽管自己的实现没有那么优美，但是进行了有益的尝试和练习，感觉也是有收获的呵

 

protected HashMap<Integer, Integer> anchor; protected int cost; protected int[] numbers; protected int[] mark; public int cost(int[] numbers) { this.mark = new int[numbers.length]; this.anchor = new HashMap<Integer, Integer>(); this.numbers = numbers; // Target list in order ArrayList<Integer> target = new ArrayList<Integer>(); for(int i=0; i<numbers.length; i++) target.add(numbers[i]); Collections.sort(target); // Anchor list int minIndex = 0; for(int i=0; i<numbers.length; i++) { anchor.put(numbers[i], target.indexOf(numbers[i])); if(numbers[i]<numbers[minIndex]) minIndex = i; } // Greedy to find a good estimated cost for search later int[] copy = new int[numbers.length]; System.arraycopy(numbers, 0, copy, 0, numbers.length); cost=0; for(int i=0; i<numbers.length; i++) { int min=Integer.MAX_VALUE, cursor=0; for(int j=i; j<numbers.length; j++) if(j!=anchor.get(copy[j])) if(min>copy[j]+copy[anchor.get(copy[j])]) { min = copy[j]+copy[anchor.get(copy[j])]; cursor = j; } if(min==Integer.MAX_VALUE) break; cost += min; int tmp = copy[cursor]; copy[cursor] = copy[anchor.get(tmp)]; copy[anchor.get(tmp)] = tmp; } // Simple search for smaller cost solve(0,0); // Swap minimal number to other position and do more simple search for(int i=0; i<numbers.length; i++) if(i!=minIndex) { numbers[i] = numbers[i]^numbers[minIndex]; numbers[minIndex] = numbers[i]^numbers[minIndex]; numbers[i] = numbers[i]^numbers[minIndex]; solve(numbers[i]+numbers[minIndex],0); numbers[i] = numbers[i]^numbers[minIndex]; numbers[minIndex] = numbers[i]^numbers[minIndex]; numbers[i] = numbers[i]^numbers[minIndex]; } return cost; } public void solve(int cost, int floor) { if(cost>=this.cost) return; if(floor==numbers.length) { this.cost = Math.min(this.cost, cost); return; } for(int i=0; i<numbers.length; i++) if(mark[i]==0) { mark[i] = 1; int swapTo=0; while(anchor.get(numbers[swapTo])!=i) swapTo++; if(swapTo==i) { solve(cost,floor+1); } else { numbers[i] = numbers[i]^numbers[swapTo]; numbers[swapTo] = numbers[i]^numbers[swapTo]; numbers[i] = numbers[i]^numbers[swapTo]; solve(cost+numbers[i]+numbers[swapTo],floor+1); numbers[i] = numbers[i]^numbers[swapTo]; numbers[swapTo] = numbers[i]^numbers[swapTo]; numbers[i] = numbers[i]^numbers[swapTo]; } mark[i] = 0; } }