JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Subsets of a Set
 Iterating Over All Subsets of a Set | Reply Problem:Iterate over all the subsets of a set.Solution:A subset of a set is a set that contains all or some of the elements of that set. For example if the set is {3, 5, 7} then some of its subsets are {} - the empty set, {3, 7}, {5, 7}, {5} and {3, 5, 7} - the original set. Often we need to find a subset with a particular property. If the original set is small, ie. has a small number of elements then it is sufficient to generate and test all its subsets. If the original set has n elements then it will contain 2^n subsets. Assuming that the computation required for each subset is small, we can usually do this for n up to 20.Let us represent a subset with a unique binary number i. This way there will be a total of 2^n such unique numbers. The k-th element of the set can be either included or not included in the subset. We can associate the inclusion of the k-th element with a value of 1 at the k-th bit of i, similarly if the k-th bit is 0 then the k-th element is not included. For example, here is how we can associate a unique binary number from 0 to 7 with every subset of {3, 5, 7}:`Binary Number Subset000 {}001 {7}010 {5}011 {5, 7}100 {3}101 {3, 7}110 {3, 5}111 {3, 5, 7}`Now all that remains is to iterate over all the subsets. Since these are just binary numbers, it suffices to iterate from 0 to 2^n-1 inclusive. In the following Java example we iterate over all the subsets of the set {"appple", "banana", "carrot"}. After generating a subset we can perform any action. Here for simplicity we print it. Notice that the 0-th subset is the empty subset, as it contains no elements.```String[] set={"apple", "banana", "carrot"}; int n=set.length;   // iterate over all the subsets for (int i=0; i < (1< 0) subset.add(set[k]); } // perform an action over the subset, here just print it System.out.print("Subset "+i+":"); for (int k=0; k 0; i2 = (i2-1) & i) { // generate the subset induced by i2 ... } } ```Warning: i=0 (empty subset) is a special case and must be treated separately.Finally, there are many other operations that can be performed on sets: union, intersection, subtraction, element addition, element deletion. All of these can be done with simple and extremely fast bitwise operations. If A and B are two sets whose bit-masks are a and b respectively then we have the following:Union of A and B: a|bIntersection of A and B: a&bA "minus" B: a&(~b). This is a set of elements in A that are not in B.Add k-th element to set A: a |= 1 << kDelete k-th element of set A: a &= ~(1 << k)For an excellent description of bitwise operations take a look at bmerry’s recipe.Now let's solve some problems that use these techniques. Let's solve BouncingBalls. For this problem, the number of balls (n<=12) is sufficiently small that we can generate all possible starting states. Each ball can be rolled either left or right, so we have 2^n possible starting states. Let dir[i] be the initial direction given to the i-th ball, 1 for right and -1 for left. A collision will occur between balls k and m if ball k is to the left of ball m (x[k]<=2*T). For each possible starting state, we count the number of possible bounces for every pair of balls k and m. To compute the expected number of bounces we divide this value by the total number of starting states (1<```public class BouncingBalls { public double expectedBounces(int[] x, int T) { int n=x.length; int bounces=0;   //iterate over all possible starting states for (int i=0; i<(1< 0) dir[k]=+1; //roll ball k right else dir[k]=-1; //roll ball k left } for (int k=0; k
 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
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Subsets of a Set Previous Thread  |  Next Thread