JOIN
 Revision History
 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 My Post History  |  My Watches  |  User Settings Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Subsets of a Set Revision History (3 edits)
 Iterating Over All Subsets of a Set 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
 Iterating Over All Subsets of a Set 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] 0) dir[k]=+1; //roll ball k right else dir[k]=-1; //roll ball k left } for (int k=0; k
 Iterating Over All Subsets of a Set 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.
 Iterating Over All Subsets of a Set 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 article “A bit of fun: fun with bits” (ADD REFERENCE HERE).