JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
Now let's solve VectorMatching. In this problem we are given n points and we are asked to find a vector matching that has the minimal length. The number of points is small (n=20) which allows us to iterate over all possible vector matchings. A vector matching consists of two sets of points A and B, such that the head of the i-th vector is the i-th point in A and its tail is the i-th point in B. A and B should have the same number of elements, namely n/2. Each point can be either in set A or in set B, so we have 2^n possible states. However, we only need to consider those states where the size of A is n/2. This reduces the problem to Choose(20,10) = 185756 states.

Suppose the point (x1,y1) is in A and the point (x2,y2) is in B. The vector represented by these two points is (x2-x1,y2-y1). Hence if a point is in A then it contributes negatively to the vector sum; otherwise it is in B and it contributes positively. So now we can determine the vector sum (which is a vector) as we iterate through the points in A and B; its x-component will be sumX and its y-component will be sumY:
public class VectorMatching
{
  public double minimumLength(int[] x, int[] y)
  {
    double result = Double.MAX_VALUE;
    int n = x.length;
    for (int i = 0; i < (1 << n); i++)
    {
      //size of A and B must be n/2
      if (2*Integer.bitCount(i) != n) continue;		
 
      long sumX = 0;
      long sumY = 0;
      for (int k = 0; k < n; k++)
      {
	//point (x[k],y[k]) is in B
	if ((i&(1<<k)) > 0)
	{
          sumX += x[k];
          sumY += y[k];
        }
	//point (x[k],y[k]) is in A
	else
	{
          sumX -= x[k];
          sumY -= y[k];
        }
      }
 
      double length=Math.sqrt(sumX*sumX + sumY*sumY);  //vector length
      result = Math.min(result,length);  //record the minimum length
    }
    return result;
  }
}
Subject Author Date
Iterating Over All Subsets of a Set dimkadimon Apr 15, 2010 at 10:02 PM EDT
Re: Iterating Over All Subsets of a Set dimkadimon Apr 15, 2010 at 10:04 PM EDT
Re: Iterating Over All Subsets of a Set Nickolas Jun 28, 2010 at 2:33 AM EDT
Re: Iterating Over All Subsets of a Set dimkadimon Sep 6, 2010 at 2:32 AM EDT
Re: Iterating Over All Subsets of a Set codersx Jan 11, 2013 at 8:43 AM EST
Re: Iterating Over All Subsets of a Set Eryx Nov 4, 2010 at 5:57 PM EDT
Re: Iterating Over All Subsets of a Set savon_cn Jun 20, 2012 at 11:05 AM EDT
Re: Iterating Over All Subsets of a Set dimkadimon Jul 26, 2012 at 1:08 AM EDT
Re: Iterating Over All Subsets of a Set holomorph Aug 8, 2012 at 1:05 PM EDT
Re: Iterating Over All Subsets of a Set d@rk_sh@dow Oct 27, 2014 at 3:09 PM EDT
Re: Iterating Over All Subsets of a Set dimkadimon Nov 9, 2014 at 3:15 AM EST
Re: Iterating Over All Subsets of a Set hacker007 Sep 9, 2012 at 7:54 AM EDT
Re: Iterating Over All Subsets of a Set MauricioC Sep 9, 2012 at 2:44 PM EDT
Re: Iterating Over All Subsets of a Set puneetm Oct 9, 2012 at 9:38 PM EDT
Re: Iterating Over All Subsets of a Set dimkadimon Oct 9, 2012 at 11:34 PM EDT
Re: Iterating Over All Subsets of a Set stubbscroll Oct 16, 2012 at 4:44 PM EDT
Re: Iterating Over All Subsets of a Set sjsupersumit Jun 5, 2014 at 8:00 AM EDT
Re: Iterating Over All Subsets of a Set d000hg Jun 9, 2014 at 9:46 AM EDT
Re: Iterating Over All Subsets of a Set ZuBruce Jan 19, 2016 at 2:03 PM EST
Re: Iterating Over All Subsets of a Set dimkadimon Jan 21, 2016 at 6:53 AM EST
RSS