/***********************************************************
 *                  5.10 圓排列問題
 * 1.問題描述
 * 給定 n 個(gè)大小不等的圓 c1, c2, c3, ..., cn, 現(xiàn)在要將這 n 個(gè)圓排進(jìn)
 * 一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從 n 個(gè)圓的
 * 所有排列中找出有最小長度的圓排列。
 *
 * 2.算法設(shè)計(jì)
 * 圓排列問題的解空間是一棵排列樹。按照回溯法搜索排列樹的算法框架，設(shè)開始
 * 時(shí) a = [r1, r2, ..., rn] 是所給的 n 個(gè)圓的半徑，則相應(yīng)的排列樹由
 * a[1, .., n] 的所有排列構(gòu)成。
 *
 * 3.復(fù)雜度
 * O(n!)
 */
public class Circles {
 static int n;   //待排列的圓的個(gè)數(shù)
 static float min;  //當(dāng)前最優(yōu)值
 static float[] x;  //當(dāng)前圓排列圓心橫坐標(biāo)
 static float[] r;  //當(dāng)前圓排列
 
 public static float circlePerm(int nn, float[] rr) {
  n = nn;
  min = Float.MAX_VALUE;
  x = new float[n];
  r = rr;
  trackback(0);
  return min;
 }

 private static void trackback(int t) {
  if (t == n - 1) {
   compute();
  } else {
   for (int j = t; j < n; j++) {
    swap(r, t, j);
    float centerx = center(t);
    if (centerx + r[t] + r[0] < min) { //下界約束
     x[t] = centerx;
     trackback(t + 1);
    }
    swap(r, t, j);
   }
  }
  
 }

 private static float center(int t) {
  //計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo)
  float temp = 0;
  for (int j = 1; j < t; j++) {
   float valuex = (float)(x[j] + 2.0 * Math.sqrt(r[t] * r[j]));
   if (valuex > temp) {
    temp = valuex;
   }
  }
  return temp;
 }

 private static void compute() {
  // 計(jì)算當(dāng)前圓排列的長度
  float low = 0;
  float high = 0;
  for (int i = 0; i < n; i++) {
   if (x[i] - r[i] < low)
    low = x[i] - r[i];
   if (x[i] + r[i] > high)
    high = x[i] + r[i];
  }
  if (high - low < min)
   min = high - low;  
 }
 
 private static void swap(float[] array, int i, int j) {
  float temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }
}