JOIN
Get Time
forums  Revision History
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 Subset
000 {}
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<<n); i++)
{
    // generate the i-th subset
    Vector subset=new Vector();
    for (int k=0; k < n; k++)
    {
        if ((i&(1<<k)) > 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<subset.size(); k++)
        System.out.print(" "+subset.get(k));
    System.out.println();
}


Discussion:
The above procedure is very useful as it can be applied to many problems. One simple extension is to only generate subsets with no more than m elements. To achieve this we can modify the i-loop so that it only iterates over i that do not have more than m bits set to 1:

// iterate over all the subsets with no more than m elements
for (int i = 0; i < (1<<n); i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1)
{
    ...
}


Let us decipher i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1. We know that i+1 can only add at most one extra bit to i. So if the number of bits in i is less than m, then i+1 will not have more than m bits. Otherwise if the number of bits in i is m, we set i to (i|(i-1))+1. This value is i plus its lowest bit, ie it is the smallest integer greater than i whose bit count is no more than i's bit count. Since i starts with 0, we can see that this approach can never lead to i that has more than m bits. Warning: this does not work for m=0.

Another trick is to iterate over all the subsets of a subset in O(3^n) time:

// iterate over all the subsets
for (int i=0; i < (1<<n); i++)
{
    // iterate over all the subsets of the i-th subset
    for(int i2 = i; i2 > 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|b
Intersection of A and B: a&b
A "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 << k
Delete 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]<x[m]), ball k is rolled right (dir[k]==1), ball m is rolled left (dir[m]==-1) and the distance that each has to roll is not more than the given time T (x[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<<n).
>
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<<n); i++)
		{
			//construct the current starting state of directions
			int[] dir=new int[n];
			for (int k=0; k<n; k++)
			{
				if ((i&(1<<k)) > 0)
					dir[k]=+1;		//roll ball k right
				else
					dir[k]=-1;		//roll ball k left
			}
			
			for (int k=0; k<n; k++)			//left ball
				for (int m=0; m<n; m++)		//right ball
					if (x[k]<x[m] && dir[k]==1 && dir[m]==-1 && x[m]-x[k] <= 2*T)
						bounces++;
		}
		
		return bounces*1.0/(1<<n);
	}
}

Note that this problem can be solved more easily without iterating over all the subsets. It can be shown that it is enough to add 0.25 for each pair of balls that are close enough. See Egor's solution that implements this idea.

EDIT: Added Eryx's suggestion.
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 Subset
000 {}
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<<n); i++)
{
    // generate the i-th subset
    Vector subset=new Vector();
    for (int k=0; k < n; k++)
    {
        if ((i&(1<<k)) > 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<subset.size(); k++)
        System.out.print(" "+subset.get(k));
    System.out.println();
}


Discussion:
The above procedure is very useful as it can be applied to many problems. One simple extension is to only generate subsets with no more than m elements. To achieve this we can modify the i-loop so that it only iterates over i that do not have more than m bits set to 1:

// iterate over all the subsets with no more than m elements
for (int i = 0; i < (1<<n); i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1)
{
    ...
}


Let us decipher i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1. We know that i+1 can only add at most one extra bit to i. So if the number of bits in i is less than m, then i+1 will not have more than m bits. Otherwise if the number of bits in i is m, we set i to (i|(i-1))+1. This value is i plus its lowest bit, ie it is the smallest integer greater than i whose bit count is no more than i's bit count. Since i starts with 0, we can see that this approach can never lead to i that has more than m bits. Warning: this does not work for m=0.

Another trick is to iterate over all the subsets of a subset in O(3^n) time:

// iterate over all the subsets
for (int i=0; i < (1<<n); i++)
{
    // iterate over all the subsets of the i-th subset
    for(int i2 = i; i2 > 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|b
Intersection of A and B: a&b
A "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 << k
Delete 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]<x[m]), ball k is rolled right (dir[k]==1), ball m is rolled left (dir[m]==-1) and the distance that each has to roll is not more than the given time T (x[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<<n).
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<<n); i++)
		{
			//construct the current starting state of directions
			int[] dir=new int[n];
			for (int k=0; k<n; k++)
			{
				if ((i&(1<<k)) > 0)
					dir[k]=+1;		//roll ball k right
				else
					dir[k]=-1;		//roll ball k left
			}
			
			for (int k=0; k<n; k++)			//left ball
				for (int m=0; m<n; m++)		//right ball
					if (x[k]<x[m] && dir[k]==1 && dir[m]==-1 && x[m]-x[k] <= 2*T)
						bounces++;
		}
		
		return bounces*1.0/(1<<n);
	}
}
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 Subset
000 {}
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<<n); i++)
{
    // generate the i-th subset
    Vector subset=new Vector();
    for (int k=0; k < n; k++)
    {
        if ((i&(1<<k)) > 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<subset.size(); k++)
        System.out.print(" "+subset.get(k));
    System.out.println();
}


Discussion:
The above procedure is very useful as it can be applied to many problems. One simple extension is to only generate subsets with no more than m elements. To achieve this we can modify the i-loop so that it only iterates over i that do not have more than m bits set to 1:

// iterate over all the subsets with no more than m elements
for (int i = 0; i < (1<<n); i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1)
{
    ...
}


Let us decipher i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1. We know that i+1 can only add at most one extra bit to i. So if the number of bits in i is less than m, then i+1 will not have more than m bits. Otherwise if the number of bits in i is m, we set i to (i|(i-1))+1. This value is i plus its lowest bit, ie it is the smallest integer greater than i whose bit count is no more than i's bit count. Since i starts with 0, we can see that this approach can never lead to i that has more than m bits. Warning: this does not work for m=0.

Another trick is to iterate over all the subsets of a subset in O(3^n) time:

// iterate over all the subsets
for (int i=0; i < (1<<n); i++)
{
    // iterate over all the subsets of the i-th subset
    for(int i2 = i; i2 > 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|b
Intersection of A and B: a&b
A "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 << k
Delete 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 Subset
000 {}
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<<n); i++)
{
    // generate the i-th subset
    Vector subset=new Vector();
    for (int k=0; k < n; k++)
    {
        if ((i&(1<<k)) > 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<subset.size(); k++)
        System.out.print(" "+subset.get(k));
    System.out.println();
}


Discussion:
The above procedure is very useful as it can be applied to many problems. One simple extension is to only generate subsets with no more than m elements. To achieve this we can modify the i-loop so that it only iterates over i that do not have more than m bits set to 1:

// iterate over all the subsets with no more than m elements
for (int i = 0; i < (1<<n); i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1)
{
    ...
}


Let us decipher i=Integer.bitCount(i) < m ? i+1 : (i|(i-1))+1. We know that i+1 can only add at most one extra bit to i. So if the number of bits in i is less than m, then i+1 will not have more than m bits. Otherwise if the number of bits in i is m, we set i to (i|(i-1))+1. This value is i plus its lowest bit, ie it is the smallest integer greater than i whose bit count is no more than i's bit count. Since i starts with 0, we can see that this approach can never lead to i that has more than m bits. Warning: this does not work for m=0.

Another trick is to iterate over all the subsets of a subset in O(3^n) time:

// iterate over all the subsets
for (int i=0; i < (1<<n); i++)
{
    // iterate over all the subsets of the i-th subset
    for(int i2 = i; i2 > 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|b
Intersection of A and B: a&b
A "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 << k
Delete 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).