function [dist, bestPts, bestInds] = getBestDistance(pts, wts)
% Gets the best average distance using one point from each group.
%
% pts: cell array of point groups.
% wts: weight for each dimension for weighted L2
%
% dist: Best distance
% bestPts: Points giving best distance
% bestInds: Indexes of points giving best distance.
%
% Author: saurabh.me@gmail.com (Saurabh Singh)

inds = zeros(1, length(pts));
[dist, bestPts, bestInds] = getBestDist(pts, wts, inds, 1);
end

function [dist, bestPt, bestInds] = getBestDist(pts, wts, inds, level)
if level > length(pts)
  % Base case
  p = zeros(length(pts), size(pts{1}, 2));
  for i = 1 : length(inds)
    p(i, :) = pts{i}(inds(i), :);
  end
  m = mean(p);
  d = p - repmat(m, size(p, 1), 1);
  w = repmat(wts, size(p, 1), 1);
  dist = sum(sum(d .* d .* w, 2)) / size(p, 1);
  bestPt = p;
  bestInds = inds;
else
  % Calculate dist for all points
  dist = intmax('int64');
  bestPt = [];
  for i = 1 : size(pts{level}, 1)
    inds(level) = i;
    [tmpDist, tmpPt, tmpInds] = getBestDist(pts, wts, inds, level + 1);
    if tmpDist < dist
      dist = tmpDist;
      bestPt = tmpPt;
      bestInds = tmpInds;
    end
  end
end
end